1<html><head><!-- Copyright 2007 Aaron Windsor 2 3 Distributed under the Boost Software License, Version 1.0. 4 (See accompanying file LICENSE_1_0.txt or copy at 5 http://www.boost.org/LICENSE_1_0.txt) 6 7 --><title>Boost Graph Library: Planar Canonical Ordering</title> 8</head> 9<body alink="#ff0000" 10 bgcolor="#ffffff" 11 link="#0000ee" 12 text="#000000" 13 vlink="#551a8b"> 14<img src="../../../boost.png" alt="C++ Boost" height="86" width="277"> 15 16<br clear=""> 17 18<h1>Planar Canonical Ordering</h1> 19 20<pre>template <typename Graph, typename PlanarEmbedding, typename OutputIterator, typename VertexIndexMap> 21void planar_canonical_ordering(const Graph& g, PlanarEmbedding embedding, OutputIterator ordering, VertexIndexMap vm); 22</pre> 23 24<p> 25A <i>planar canonical ordering</i> is an ordering <i>v<sub>1</sub>, 26v<sub>2</sub>, ..., v<sub>n</sub></i> of the vertices of a 27<a href="make_maximal_planar.html">maximal</a> 28<a href="planar_graphs.html">planar</a> graph having the property that, for 29each <i>k</i>, <i>3 <= k < n</i>, the graph induced by 30<i>v<sub>1</sub>, v<sub>2</sub>, ..., v<sub>k</sub></i> 31</p><ul> 32<li>is biconnected and contains the edge <i>{v<sub>1</sub>, v<sub>2</sub>}</i> 33on its outer face. 34</li><li>has any vertices in the range <i>v<sub>1</sub>, v<sub>2</sub>, ..., 35v<sub>k</sub></i> that are adjacent to <i>v<sub>(k+1)</sub></i> on its outer 36face, and these vertices form a path along the outer face. 37</li></ul> 38 39Let <i>G<sub>k</sub></i> be the graph induced by the first <i>k</i> vertices in 40the canonical ordering, along with all edges between any of the first <i>k</i> 41vertices. After <i>G<sub>k</sub></i> has been drawn, the <i>(k+1)</i>st vertex 42can be drawn easily without edge crossings, since it's adjacent only to a 43consecutive sequence of vertices on the outer face of <i>G<sub>k</sub></i>. 44<p> 45</p><blockquote> 46<center> 47<img src="./figs/canonical_ordering.png"> 48</center> 49</blockquote> 50 51A planar canonical ordering exists for every maximal planar graph with at 52least 2 vertices. <tt>planar_canonical_ordering</tt> expects the input graph 53to have at least 2 vertices. 54<p> 55 56The planar canonical ordering is used as an input in some planar graph drawing 57algorithms, particularly those that create a straight line embedding. 58de Fraysseix, Pach, and Pollack 59[<a href="./bibliography.html#defraysseixpachpollack90">72</a>] 60first proved the 61existence of such an ordering and showed how to compute one in time 62<i>O(n)</i> on a maximal planar graph with <i>n</i> vertices. 63 64 65<h3>Complexity</h3> 66If the vertex index map provides constant-time access to indices, this 67function takes time <i>O(n + m)</i> for a planar graph with <i>n</i> vertices 68and <i>m</i> edges. Note that 69in a simple planar graph with <i>f</i> faces, <i>m</i> edges, and <i>n</i> 70vertices, both <i>f</i> and <i>m</i> are <i>O(n)</i>. 71 72<h3>Where Defined</h3> 73 74<p> 75<a href="../../../boost/graph/planar_canonical_ordering.hpp"> 76<tt>boost/graph/planar_canonical_ordering.hpp</tt></a> 77 78</p><h3>Parameters</h3> 79 80IN: <tt>Graph& g</tt> 81 82<blockquote> 83An undirected graph. The graph type must be a model of 84<a href="VertexAndEdgeListGraph.html">VertexAndEdgeListGraph</a>. 85The graph must: 86<ul> 87<li>Be maximal planar.</li> 88<li>Have at least two vertices.</li> 89</ul> 90</blockquote> 91 92IN: <tt>PlanarEmbedding</tt> 93 94<blockquote> 95A model of <a href="PlanarEmbedding.html">PlanarEmbedding</a>. 96</blockquote> 97 98IN: <tt>OutputIterator</tt> 99 100<blockquote> 101An OutputIterator with <tt>value_type</tt> equal to 102<tt>graph_traits<Graph>::vertex_descriptor</tt>. The canonical ordering 103will be written to this iterator. 104</blockquote> 105 106IN: <tt>VertexIndexMap vm</tt> 107 108<blockquote> 109A <a href="../../property_map/doc/ReadablePropertyMap.html">Readable Property Map 110</a> that maps vertices from <tt>g</tt> to distinct integers in the range 111<tt>[0, num_vertices(g) )</tt><br> 112<b>Default</b>: <tt>get(vertex_index,g)</tt><br> 113</blockquote> 114 115<h3>Example</h3> 116 117<p> 118<a href="../example/canonical_ordering.cpp"> 119<tt>examples/canonical_ordering.cpp</tt></a> 120 121</p><h3>See Also</h3> 122 123<p> 124<a href="planar_graphs.html">Planar Graphs in the Boost Graph Library</a> 125 126<br> 127</p><hr> 128Copyright � 2007 Aaron Windsor (<a href="mailto:aaron.windsor@gmail.com"> 129aaron.windsor@gmail.com</a>) 130 131</body></html> 132
