2 <!-- Copyright 2007 Aaron Windsor
4 Distributed under the Boost Software License, Version 1.0.
5 (See accompanying file LICENSE_1_0.txt or copy at
6 http://www.boost.org/LICENSE_1_0.txt)
10 <Title>Boost Graph Library: make_maximal_planar
</Title>
11 <BODY BGCOLOR=
"#ffffff" LINK=
"#0000ee" TEXT=
"#000000" VLINK=
"#551a8b"
13 <IMG SRC=
"../../../boost.png"
14 ALT=
"C++ Boost" width=
"277" height=
"86">
18 <H1><tt>make_maximal_planar
</tt></H1>
23 template
<typename Graph, typename PlanarEmbedding, typename VertexIndexMap, typename EdgeIndexMap, typename AddEdgeVisitor
>
24 void make_maximal_planar(Graph& g, PlanarEmbedding embedding, VertexIndexMap vm, EdgeIndexMap em, AddEdgeVisitor vis);
28 A
<a href=
"planar_graphs.html">planar graph
</a> <i>G
</i> is
29 <i>maximal planar
</i> if no additional edges (except parallel edges and
30 self-loops) can be added to
<i>G
</i> without creating a non-planar graph. By
31 <a href=
"planar_graphs.html#EulersFormula">Euler's formula
</a>, a maximal
32 planar graph on
<i>n
</i> vertices (
<i>n
> 2</i>) always has
<i>3n -
6</i> edges
34 <i>2n -
4</i> faces. The input graph to
<tt>make_maximal_planar
</tt> must be a
35 <a href=
"make_biconnected_planar.html">biconnected
</a> planar graph with at
38 The default behavior of
<tt>make_maximal_planar
</tt> is to modify the graph
39 <tt>g
</tt> by calling
<tt>add_edge(u,v,g)
</tt> for every pair of vertices
40 <i>(u,v)
</i> where an edge needs to be added to make
<tt>g
</tt> maximal planar.
41 This behavior can be overriden by providing a vistor as the
42 <tt>AddEdgeVisitor
</tt> parameter. The only requirement for an
43 <tt>AddEdgeVisitor
</tt> is that it define a member function with the following
46 template
<typename Graph, typename Vertex
>
47 void visit_vertex_pair(Vertex u, Vertex v, Graph& g);
49 This event point can also be used as a hook to update the underlying edge
50 index map automatically as edges are added. See the
51 documentation for the
<a href=
"./AddEdgeVisitor.html">AddEdgeVisitor
</a>
52 concept for more information.
54 <H3>Where Defined
</H3>
57 <a href=
"../../../boost/graph/make_maximal_planar.hpp">
58 <TT>boost/graph/make_maximal_planar.hpp
</TT>
63 IN/OUT:
<tt>Graph
& g
</tt>
66 An undirected graph. The graph type must be a model of
<a
67 href=
"VertexListGraph.html">Vertex List Graph
</a>,
<a
68 href=
"IncidenceGraph.html">Incidence Graph
</a>, and
69 a
<a href=
"MutableGraph.html">Mutable Graph
</a><br>
72 IN:
<tt>PlanarEmbedding embedding
</tt>
75 A
<a href=
"../../property_map/doc/ReadablePropertyMap.html">Readable Property Map
76 </a> that models the
<a href=
"PlanarEmbedding.html">PlanarEmbedding
</a>
80 IN:
<tt>VertexIndexMap vm
</tt>
83 A
<a href=
"../../property_map/doc/ReadablePropertyMap.html">Readable Property Map
84 </a> that maps vertices from
<tt>g
</tt> to distinct integers in the range
85 <tt>[
0, num_vertices(g) )
</tt><br>
86 <b>Default
</b>:
<tt>get(vertex_index,g)
</tt><br>
89 IN:
<tt>EdgeIndexMap vm
</tt>
92 A
<a href=
"../../property_map/doc/ReadablePropertyMap.html">Readable Property Map
93 </a> that maps edges from
<tt>g
</tt> to distinct integers in the range
94 <tt>[
0, num_edges(g) )
</tt><br>
95 <b>Default
</b>:
<tt>get(edge_index,g)
</tt><br>
98 IN:
<tt>AddEdgeVisitor vis
</tt>
101 A model of
<a href=
"AddEdgeVisitor.html">AddEdgeVisitor
</a>.
<br>
102 <b>Default
</b>:
<tt>default_add_edge_visitor
</tt>, a class defines
103 <tt>visit_vertex_pair
</tt> to dispatch its calls to
<tt>add_edge
</tt>.
109 On a graph with
<i>n
</i> vertices and
<i>m
</i> edges,
110 <tt>make_maximal_planar
</tt> runs in time
<i>O(n + m)
</i>
115 <a href=
"../example/make_maximal_planar.cpp">
116 <TT>examples/make_maximal_planar.cpp
</TT>
121 <a href=
"planar_graphs.html">Planar Graphs in the Boost Graph Library
</a>
125 Copyright
© 2007 Aaron Windsor (
<a href=
"mailto:aaron.windsor@gmail.com">
126 aaron.windsor@gmail.com
</a>)