make_biconnected_planar

Adds edges to a connected planar graph to make it biconnected while preserving planarity.

Complexity: O(n)
Defined in: <boost/graph/make_biconnected_planar.hpp>

Example

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/boyer_myrvold_planar_test.hpp>
#include <boost/graph/make_biconnected_planar.hpp>
#include <iostream>
#include <vector>

using namespace boost;

// Bundled edge field holds the contiguous index that planar algorithms need.
struct Edge { int idx; };

using Graph = adjacency_list<vecS, vecS, undirectedS, no_property, Edge>;
using Descriptor = graph_traits<Graph>::edge_descriptor;

void reindex(Graph& g) {
    int i = 0;
    for (auto e : make_iterator_range(edges(g))) { g[e].idx = i++; }
}

int main() {
    // A path graph: 0-1-2-3 (planar but not biconnected)
    Graph g(4);
    add_edge(0, 1, g); add_edge(1, 2, g); add_edge(2, 3, g);

    reindex(g);

    // Compute planar embedding
    using EmbStorage = std::vector<std::vector<Descriptor>>;
    EmbStorage storage(num_vertices(g));
    auto embedding = make_iterator_property_map(storage.begin(), get(vertex_index, g));
    boyer_myrvold_planarity_test(boyer_myrvold_params::graph = g,
        boyer_myrvold_params::embedding = embedding);

    std::cout << "Edges before: " << num_edges(g) << "\n";
    reindex(g);
    make_biconnected_planar(g, embedding, get(&Edge::idx, g));
    std::cout << "Edges after make_biconnected_planar: " << num_edges(g) << "\n";
}

Edges before: 3
Edges after make_biconnected_planar: 5

Synopsis

template <typename Graph, typename PlanarEmbedding,
          typename EdgeIndexMap, typename AddEdgeVisitor>
void make_biconnected_planar(
    Graph& g,
    PlanarEmbedding embedding,
    EdgeIndexMap em,
    AddEdgeVisitor& vis);

Direction Parameter Description

Direction	Parameter	Description
IN/OUT	`Graph& g`	An undirected graph. The type `Graph` must be a model of VertexListGraph, IncidenceGraph, and MutableGraph.
IN	`PlanarEmbedding embedding`	A model of PlanarEmbedding.
IN	`EdgeIndexMap em`	A Readable Property Map that maps edges from `g` to distinct integers in the range `[0, num_edges(g))`. Default: `get(edge_index, g)`
IN	`AddEdgeVisitor& vis`	A model of AddEdgeVisitor. Default: `default_add_edge_visitor`, a class that defines `visit_vertex_pair` to dispatch its calls to `add_edge`.

IN/OUT

Graph& g

An undirected graph. The type Graph must be a model of VertexListGraph, IncidenceGraph, and MutableGraph.

PlanarEmbedding embedding

A model of PlanarEmbedding.

EdgeIndexMap em

A Readable Property Map that maps edges from g to distinct integers in the range [0, num_edges(g)).
Default: get(edge_index, g)

AddEdgeVisitor& vis

A model of AddEdgeVisitor.
Default: default_add_edge_visitor, a class that defines visit_vertex_pair to dispatch its calls to add_edge.

Description

A graph G is biconnected if, for every pair of vertices u,v in G, there is a cycle containing both u and v. Alternatively, a graph is biconnected if it is connected and cannot be made disconnected by removing any single vertex. make_biconnected_planar takes a connected planar graph g as input and adds zero or more edges to make g biconnected while preserving planarity.

The default behavior of make_biconnected_planar is to modify the graph g by calling add_edge(u,v,g) for every pair of vertices (u,v) where an edge needs to be added to make g biconnected. This behavior can be overridden by providing a visitor as the AddEdgeVisitor parameter. The only requirement for an AddEdgeVisitor is that it define a member function with the following signature:

template <typename Graph, typename Vertex>
void visit_vertex_pair(Vertex u, Vertex v, Graph& g);

This event point can also be used as a hook to update the underlying edge index map automatically as edges are added. See the documentation for the AddEdgeVisitor concept for more information.

Edit this Page