make_maximal_planar

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

A planar graph G is maximal planar if no additional edges (except parallel edges and self-loops) can be added to G without creating a non-planar graph. By Euler's formula, a maximal planar graph on n vertices (n > 2) always has 3n - 6 edges and 2n - 4 faces. The input graph to make_maximal_planar must be a biconnected planar graph with at least 3 vertices.

The default behavior of make_maximal_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 maximal planar. 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);

Where Defined

boost/graph/make_maximal_planar.hpp

Parameters

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

A Readable Property Map that models the PlanarEmbedding concept.

A Readable Property Map that maps vertices from g to distinct integers in the range [0, num_vertices(g) )
Default: get(vertex_index,g)

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

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

Complexity

Example

examples/make_maximal_planar.cpp

See Also