1<HTML> 2<!-- Copyright 2007 Aaron Windsor 3 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) 7 8 --> 9<Head> 10<Title>Boost Graph Library: make_maximal_planar</Title> 11<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b" 12 ALINK="#ff0000"> 13<IMG SRC="../../../boost.png" 14 ALT="C++ Boost" width="277" height="86"> 15 16<BR Clear> 17 18<H1><tt>make_maximal_planar</tt></H1> 19 20<p> 21 22<pre> 23template <typename Graph, typename PlanarEmbedding, typename VertexIndexMap, typename EdgeIndexMap, typename AddEdgeVisitor> 24void make_maximal_planar(Graph& g, PlanarEmbedding embedding, VertexIndexMap vm, EdgeIndexMap em, AddEdgeVisitor vis); 25</pre> 26 27<p> 28A <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 30self-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 32planar graph on <i>n</i> vertices (<i>n > 2</i>) always has <i>3n - 6</i> edges 33 and 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 36least 3 vertices. 37<p> 38The 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. 41This 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 44signature: 45<pre> 46template <typename Graph, typename Vertex> 47void visit_vertex_pair(Vertex u, Vertex v, Graph& g); 48</pre> 49This event point can also be used as a hook to update the underlying edge 50index map automatically as edges are added. See the 51documentation for the <a href="./AddEdgeVisitor.html">AddEdgeVisitor</a> 52concept for more information. 53 54<H3>Where Defined</H3> 55 56<P> 57<a href="../../../boost/graph/make_maximal_planar.hpp"> 58<TT>boost/graph/make_maximal_planar.hpp</TT> 59</a> 60 61<h3>Parameters</h3> 62 63IN/OUT: <tt>Graph& g</tt> 64 65<blockquote> 66An undirected graph. The graph type must be a model of <a 67href="VertexListGraph.html">Vertex List Graph</a>, <a 68href="IncidenceGraph.html">Incidence Graph</a>, and 69a <a href="MutableGraph.html">Mutable Graph</a><br> 70</blockquote> 71 72IN: <tt>PlanarEmbedding embedding</tt> 73 74<blockquote> 75A <a href="../../property_map/doc/ReadablePropertyMap.html">Readable Property Map 76</a> that models the <a href="PlanarEmbedding.html">PlanarEmbedding</a> 77concept. 78</blockquote> 79 80IN: <tt>VertexIndexMap vm</tt> 81 82<blockquote> 83A <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> 87</blockquote> 88 89IN: <tt>EdgeIndexMap vm</tt> 90 91<blockquote> 92A <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> 96</blockquote> 97 98IN: <tt>AddEdgeVisitor vis</tt> 99 100<blockquote> 101A 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>. 104</blockquote> 105 106 107<h3>Complexity</h3> 108 109On 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> 111 112<H3>Example</H3> 113 114<P> 115<a href="../example/make_maximal_planar.cpp"> 116<TT>examples/make_maximal_planar.cpp</TT> 117</a> 118 119<h3>See Also</h3> 120 121<a href="planar_graphs.html">Planar Graphs in the Boost Graph Library</a> 122 123<br> 124<HR> 125Copyright © 2007 Aaron Windsor (<a href="mailto:aaron.windsor@gmail.com"> 126aaron.windsor@gmail.com</a>) 127</BODY> 128</HTML> 129
