...one of the most highly
regarded and expertly designed C++ library projects in the
world. — Herb Sutter and Andrei
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);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.
An undirected graph. The graph type must be a model of Vertex List Graph, Incidence Graph, and a Mutable GraphIN: PlanarEmbedding embedding
A Readable Property Map that models the PlanarEmbedding concept.IN: VertexIndexMap vm
A Readable Property Map that maps vertices from g to distinct integers in the range [0, num_vertices(g) )IN: EdgeIndexMap vm
A Readable Property Map that maps edges from g to distinct integers in the range [0, num_edges(g) )IN: AddEdgeVisitor vis
A model of AddEdgeVisitor.
Default: default_add_edge_visitor, a class defines visit_vertex_pair to dispatch its calls to add_edge.