Boost Graph Library: make_biconnected_planar

# `make_biconnected_planar`

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

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 overriden by providing a vistor 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.

### Where Defined

`boost/graph/make_biconnected_planar.hpp`

### Parameters

IN/OUT: `Graph& g`

> An undirected graph. The graph type must be a model of Vertex List Graph, Incidence Graph, and a Mutable Graph

IN: `PlanarEmbedding embedding`

> A model of PlanarEmbedding.

IN: `EdgeIndexMap vm`

> 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`

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

### Complexity

On a planar graph with n vertices, `make_biconnected_planar` runs in time O(n)

### Example

`examples/make_biconnected_planar.cpp`

### See Also

Planar Graphs in the Boost Graph Library

Copyright © 2007 Aaron Windsor ( aaron.windsor@gmail.com)