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

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

**Default**: `get(vertex_index,g)`

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 vis`
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 graph with *n* vertices and *m* edges,
`make_maximal_planar` runs in time *O(n + m)*
### Example

`examples/make_maximal_planar.cpp`

### See Also

Planar Graphs in the Boost Graph Library

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