ceph/src/boost/libs/graph/doc/boyer_myrvold.html

   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: Boyer-Myrvold Planarity Testing/Embedding</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>Boyer-Myrvold Planarity Testing/Embedding</H1>
  19
  20 <p>
  21 A graph is <a href="./planar_graphs.html#planar"><i>planar</i></a> if it can
  22 be drawn in two-dimensional space without any of its edges crossing. Such a
  23 drawing of a planar graph is called a
  24 <a href="./planar_graphs.html#plane_drawing"><i>plane drawing</i></a>. Each
  25 plane drawing belongs to an equivalence class called a <i>planar embedding</i>
  26 <a href="#1">[1]</a> that is defined by the clockwise ordering of adjacent
  27 edges around each vertex in the graph. A planar embedding is a convenient
  28 intermediate representation of an actual drawing of a planar graph, and many
  29 planar graph drawing algorithms are formulated as functions mapping a planar
  30 embedding to a plane drawing.
  31 <br>
  32 <br>
  33 <table align="center" class="image">
  34 <caption align="bottom"><h5>A planar graph (top left), along with a planar
  35 embedding of that graph (bottom left) can be used to create a plane drawing
  36 (right) by embedding edges around each vertex in the order in which they
  37 appear in the planar embedding.
  38 </h5></caption>
  39 <tr><td>
  40 <img src="./figs/embedding_illustration.png">
  41 </td></tr>
  42 <tr></tr>
  43 <tr></tr>
  44 </table>
  45 <br>
  46 <p>
  47 The function <tt>boyer_myrvold_planarity_test</tt> implements the planarity
  48 testing/embedding algorithm of Boyer and Myrvold
  49 [<a href="./bibliography.html#boyermyrvold04">70</a>].
  50 <tt>boyer_myrvold_planarity_test</tt> returns <tt>true</tt> if the input graph
  51 is planar and <tt>false</tt> otherwise. As a side-effect of this test, a planar
  52 embedding can be constructed if the graph is planar or a minimal set of edges
  53 that form a <a href = "./planar_graphs.html#kuratowskisubgraphs">Kuratowski
  54 subgraph</a> can be found if the graph is not planar.
  55 <tt>boyer_myrvold_planarity_test</tt> uses named parameter arguments (courtesy
  56 of the <a href="../../parameter/doc/html/index.html">Boost.Parameter</a>
  57 library) to specify what the function actually does. Some examples are:
  58
  59 <ul>
  60 <li>Testing whether or not a graph is planar:
  61 <pre>
  62 bool is_planar = boyer_myrvold_planarity_test(g);
  63 </pre>
  64
  65 <li>Computing a planar embedding for a graph if it is planar, otherwise finding
  66 a set of edges that forms an obstructing Kuratowski subgraph:
  67 <pre>
  68 if (boyer_myrvold_planarity_test(boyer_myrvold_params::graph = g,
  69                                  boyer_myrvold_params::embedding = embedding_pmap,
  70                                  boyer_myrvold_params::kuratowski_subgraph = out_itr
  71                                  )
  72     )
  73 {
  74   //do something with the embedding in embedding_pmap
  75 }
  76 else
  77 {
  78   //do something with the kuratowski subgraph output to out_itr
  79 }
  80 </pre>
  81 </ul>
  82
  83 <p>
  84 The parameters passed to <tt>boyer_myrvold_planarity_test</tt> in the examples
  85 above do more than just carry the data structures used for input and output -
  86 the algorithm is optimized at compile time based on which parameters are
  87 present. A complete list of parameters accepted and their interactions are
  88 described below.
  89 <p>
  90 <tt>boyer_myrvold_planarity_test</tt> accepts as input any undirected graph,
  91 even those with self-loops and multiple edges.
  92 However, many planar graph drawing algorithms make additional restrictions
  93 on the structure of the input graph - for example, requiring that the input
  94 graph is connected, biconnected, or even maximal planar (triangulated.)
  95 Fortunately, any planar graph on <i>n</i> vertices that lacks one of these
  96 properties can be augmented with additional edges so that it satisfies that
  97 property in <i>O(n)</i> time - the functions
  98 <tt><a href="./make_connected.html">make_connected</a></tt>,
  99 <tt><a href="./make_biconnected_planar.html">make_biconnected_planar</a></tt>,
 100 and <tt><a href="./make_maximal_planar.html">make_maximal_planar</a></tt>
 101 exist for this purpose. If the graph drawing algorithm you're using requires,
 102 say, a biconnected graph, then you must make your input graph biconnected
 103 <i>before</i> passing it into <tt>boyer_myrvold_planarity_test</tt> so that the
 104 computed planar embedding includes these additional edges. This may require
 105 more than one call to <tt>boyer_myrvold_planarity_test</tt> depending on the
 106 structure of the graph you begin with, since both
 107 <tt>make_biconnected_planar</tt> and <tt>make_maximal_planar</tt> require a
 108 planar embedding of the existing graph as an input parameter.
 109
 110 <p><p>
 111 The named parameters accepted by <tt>boyer_myrvold_planarity_test</tt> are:
 112
 113 <ul>
 114 <li><b><tt>graph</tt></b> : The input graph - this is the only required
 115 parameter.
 116 <li><b><tt>vertex_index_map</tt></b> : A mapping from vertices of the input
 117 graph to indexes in the range <tt>[0..num_vertices(g))</tt>. If this parameter
 118 is not provided, the vertex index map is assumed to be available as an interior
 119 property of the graph, accessible by calling <tt>get(vertex_index, g)</tt>.
 120 <li><b><tt>edge_index_map</tt></b>: A mapping from the edges of the input graph
 121 to indexes in the range <tt>[0..num_edges(g))</tt>. This parameter is only
 122 needed if the <tt>kuratowski_subgraph</tt> argument is provided. If the
 123 <tt>kuratowski_subgraph</tt> argument is provided and this parameter is not
 124 provided, the EdgeIndexMap is assumed to be available as an interior property
 125 accessible by calling <tt>get(edge_index, g)</tt>.
 126 <li><b><tt>embedding</tt></b> : If the graph is planar, this will be populated
 127 with a mapping from vertices to the clockwise order of neighbors in the planar
 128 embedding.
 129 <li><b><tt>kuratowski_subgraph</tt></b> : If the graph is not planar, a minimal
 130 set of edges that form the obstructing Kuratowski subgraph will be written to
 131 this iterator.
 132 </ul>
 133
 134 These named parameters all belong to the namespace
 135 <tt>boyer_myrvold_params</tt>. See below for more information on the concepts
 136 required for these arguments.
 137
 138 <H3>Verifying the output</H3>
 139
 140 Whether or not the input graph is planar, <tt>boyer_myrvold_planarity_test</tt>
 141 can produce a certificate that can be automatically checked to verify that the
 142 function is working properly.
 143 <p>
 144 If the graph is planar, a planar embedding can be produced. The
 145 planar embedding can be verified by passing it to a plane drawing routine
 146 (such as <tt><a href="straight_line_drawing.html">
 147 chrobak_payne_straight_line_drawing</a></tt>) and using the function
 148 <tt><a href="is_straight_line_drawing.html">is_straight_line_drawing</a></tt>
 149 to verify that the resulting graph is planar.
 150 <p>
 151 If the graph is not planar, a set of edges that forms a Kuratowski subgraph in
 152 the original graph can be produced. This set of edges can be passed to the
 153 function <tt><a href="is_kuratowski_subgraph.html">is_kuratowski_subgraph</a>
 154 </tt> to verify that they can be contracted into a <i>K<sub>5</sub></i> or
 155 <i>K<sub>3,3</sub></i>. <tt>boyer_myrvold_planarity_test</tt> chooses the set
 156 of edges forming the Kuratowski subgraph in such a way that the contraction to
 157 a <i>K<sub>5</sub></i> or <i>K<sub>3,3</sub></i> can be done by a simple
 158 deterministic process which is described in the documentation to
 159 <tt>is_kuratowski_subgraph</tt>.
 160
 161 <H3>Where Defined</H3>
 162
 163 <P>
 164 <a href="../../../boost/graph/boyer_myrvold_planar_test.hpp">
 165 <TT>boost/graph/boyer_myrvold_planar_test.hpp</TT>
 166 </a>
 167
 168 <H3>Parameters</H3>
 169
 170 IN: <tt>Graph&amp; g</tt>
 171
 172 <blockquote>
 173 Any undirected graph. The graph type must be a model of
 174 <a href="VertexAndEdgeListGraph.html">VertexAndEdgeListGraph</a> and
 175 <a href="IncidenceGraph.html">IncidenceGraph</a>.
 176 </blockquote>
 177
 178 OUT <tt>PlanarEmbedding embedding</tt>
 179
 180 <blockquote>
 181 Must model the <a href="PlanarEmbedding.html">PlanarEmbedding</a> concept.
 182 </blockquote>
 183
 184 IN <tt>OutputIterator kuratowski_subgraph</tt>
 185
 186 <blockquote>
 187 An OutputIterator which accepts values of the type
 188 <tt>graph_traits&lt;Graph&gt;::edge_descriptor</tt>
 189 </blockquote>
 190
 191 IN <tt>VertexIndexMap vm</tt>
 192
 193 <blockquote>
 194 A <a href="../../property_map/doc/ReadablePropertyMap.html">Readable Property Map
 195 </a> that maps vertices from <tt>g</tt> to distinct integers in the range
 196 <tt>[0, num_vertices(g) )</tt><br>
 197 <b>Default</b>: <tt>get(vertex_index,g)</tt><br>
 198 </blockquote>
 199
 200 IN <tt>EdgeIndexMap em</tt>
 201
 202 <blockquote>
 203 A <a href="../../property_map/doc/ReadablePropertyMap.html">Readable Property Map
 204 </a> that maps edges from <tt>g</tt> to distinct integers in the range
 205 <tt>[0, num_edges(g) )</tt><br>
 206 <b>Default</b>: <tt>get(edge_index,g)</tt>, but this parameter is only used if
 207 the <tt>kuratowski_subgraph_iterator</tt> is provided.<br>
 208 </blockquote>
 209
 210 <H3>Complexity</H3>
 211
 212 Assuming that both the vertex index and edge index supplied take time
 213 <i>O(1)</i> to return an index and there are <i>O(n)</i>
 214 total self-loops and parallel edges in the graph, most combinations of
 215 arguments given to
 216 <tt>boyer_myrvold_planarity_test</tt> result in an algorithm that runs in time
 217 <i>O(n)</i> for a graph with <i>n</i> vertices and <i>m</i> edges. The only
 218 exception is when Kuratowski subgraph isolation is requested for a dense graph
 219 (a graph with <i>n = o(m)</i>) - the running time will be <i>O(n+m)</i>
 220 <a href = "#2">[2]</a>.
 221
 222 <H3>Examples</H3>
 223
 224 <P>
 225 <ul>
 226 <li><a href="../example/simple_planarity_test.cpp">A simple planarity test</a>
 227 <li><a href="../example/kuratowski_subgraph.cpp">Isolating a Kuratowski
 228 Subgraph</a>
 229 <li><a href="../example/straight_line_drawing.cpp">Using a planar embedding to
 230 create a straight line drawing</a>
 231 </ul>
 232
 233 <h3>See Also</h3>
 234
 235 <a href="./planar_graphs.html">Planar Graphs in the Boost Graph Library</a>
 236
 237
 238 <h3>Notes</h3>
 239
 240 <p><a name="1">[1] A planar embedding is also called a <i>combinatorial
 241 embedding</i>.
 242
 243 <p><a name="2">[2] The algorithm can still be made to run in time <i>O(n)</i>
 244 for this case, if needed. <a href="planar_graphs.html#EulersFormula">Euler's
 245 formula</a> implies that a planar graph with <i>n</i> vertices can have no more
 246 than <i>3n - 6</i> edges, which means that any non-planar graph on <i>n</i>
 247 vertices has a subgraph of only <i>3n - 5</i> edges that contains a Kuratowski
 248 subgraph. So, if you need to find a Kuratowski subgraph of a graph with more
 249 than <i>3n - 5</i> edges in time <i>O(n)</i>, you can create a subgraph of the
 250 original graph consisting of any arbitrary <i>3n - 5</i> edges and pass that
 251 graph to <tt>boyer_myrvold_planarity_test</tt>.
 252
 253
 254 <br>
 255 <HR>
 256 Copyright &copy; 2007 Aaron Windsor (<a href="mailto:aaron.windsor@gmail.com">
 257 aaron.windsor@gmail.com</a>)
 258 </BODY>
 259 </HTML>