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> 21 void planar_canonical_ordering(const Graph& g, PlanarEmbedding embedding, OutputIterator ordering, VertexIndexMap vm); 22 </pre> 23 24 <p> 25 A <i>planar canonical ordering</i> is an ordering <i>v<sub>1</sub>, 26 v<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 29 each <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> 33 on its outer face. 34 </li><li>has any vertices in the range <i>v<sub>1</sub>, v<sub>2</sub>, ..., 35 v<sub>k</sub></i> that are adjacent to <i>v<sub>(k+1)</sub></i> on its outer 36 face, and these vertices form a path along the outer face. 37 </li></ul> 38 39 Let <i>G<sub>k</sub></i> be the graph induced by the first <i>k</i> vertices in 40 the canonical ordering, along with all edges between any of the first <i>k</i> 41 vertices. After <i>G<sub>k</sub></i> has been drawn, the <i>(k+1)</i>st vertex 42 can be drawn easily without edge crossings, since it's adjacent only to a 43 consecutive 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 51 A planar canonical ordering exists for every maximal planar graph with at 52 least 2 vertices. <tt>planar_canonical_ordering</tt> expects the input graph 53 to have at least 2 vertices. 54 <p> 55 56 The planar canonical ordering is used as an input in some planar graph drawing 57 algorithms, particularly those that create a straight line embedding. 58 de Fraysseix, Pach, and Pollack 59 [<a href="./bibliography.html#defraysseixpachpollack90">72</a>] 60 first proved the 61 existence 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> 66 If the vertex index map provides constant-time access to indices, this 67 function takes time <i>O(n + m)</i> for a planar graph with <i>n</i> vertices 68 and <i>m</i> edges. Note that 69 in a simple planar graph with <i>f</i> faces, <i>m</i> edges, and <i>n</i> 70 vertices, 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 80 IN: <tt>Graph& g</tt> 81 82 <blockquote> 83 An undirected graph. The graph type must be a model of 84 <a href="VertexAndEdgeListGraph.html">VertexAndEdgeListGraph</a>. 85 The graph must: 86 <ul> 87 <li>Be maximal planar.</li> 88 <li>Have at least two vertices.</li> 89 </ul> 90 </blockquote> 91 92 IN: <tt>PlanarEmbedding</tt> 93 94 <blockquote> 95 A model of <a href="PlanarEmbedding.html">PlanarEmbedding</a>. 96 </blockquote> 97 98 IN: <tt>OutputIterator</tt> 99 100 <blockquote> 101 An OutputIterator with <tt>value_type</tt> equal to 102 <tt>graph_traits<Graph>::vertex_descriptor</tt>. The canonical ordering 103 will be written to this iterator. 104 </blockquote> 105 106 IN: <tt>VertexIndexMap vm</tt> 107 108 <blockquote> 109 A <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> 128 Copyright � 2007 Aaron Windsor (<a href="mailto:aaron.windsor@gmail.com"> 129 aaron.windsor@gmail.com</a>) 130 131 </body></html> 132
