ceph/src/boost/libs/graph/doc/planar_graphs.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: Planar Graphs</TITLE>
  11 </HEAD>
  12 <BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
  13         ALINK="#ff0000">
  14 <IMG SRC="../../../boost.png"
  15      ALT="C++ Boost" width="277" height="86">
  16
  17 <BR Clear>
  18
  19 <H1>Planar Graphs</H1>
  20
  21 <p>
  22 A graph is <a name="planar"><i>planar</i></a> if it can be drawn in
  23 two-dimensional space with no two of its edges crossing. Such a drawing of a
  24 planar graph is called a <a name="plane_drawing"><i>plane drawing</i></a>.
  25 Every planar graph also admits a <i>straight-line drawing</i>, which is a
  26 plane drawing where each edge is represented by a line segment.
  27
  28 <br>
  29 <br>
  30 <table class="image" align="center">
  31 <caption align="bottom">
  32 <h5>A planar graph (left), a plane drawing (center), and a straight line
  33 drawing (right), all of the same graph</h5>
  34 </caption>
  35 <tr>
  36 <td>
  37 <img src="./figs/planar_plane_straight_line.png">
  38 </td>
  39 </tr>
  40 <tr></tr>
  41 <table>
  42 <br>
  43
  44 Two examples of non-planar graphs are K<sub>5</sub>, the complete graph on
  45 five vertices, and K<sub>3,3</sub>, the complete bipartite graph on six
  46 vertices with three vertices in each bipartition. No matter how the vertices
  47 of either graph are arranged in the plane, at least two edges are forced to
  48 cross.
  49
  50 <a name = "kuratowskisubgraphs">
  51 <br>
  52 <br>
  53 <table class="image" align="center">
  54 <caption align="bottom"><h5>K<sub>5</sub> (left) and K<sub>3,3</sub> (right) -
  55 the two Kuratowski subgraphs</h5>
  56 </caption>
  57 <tr>
  58 <td>
  59 <img src="./figs/k_5_and_k_3_3.png">
  60 </td>
  61 </tr>
  62 </table>
  63 <br>
  64
  65 The above graphs are both minimal examples of non-planarity within
  66 their class of graphs; delete any edge or vertex from either one and the
  67 resulting graph is planar. A theorem of Kuratowski singles these two graphs
  68 out as fundamental obstructions to planarity within any graph:
  69 <blockquote>
  70 <i>
  71 A graph is planar if and only if it does not contain a subgraph that is an
  72 expansion<a href="#1">[1]</a> of either K<sub>5</sub> or K<sub>3,3</sub>
  73 </i>
  74 </blockquote>
  75
  76 <p>
  77 A subgraph that is an expansion of K<sub>5</sub> or K<sub>3,3</sub> is called
  78 a <a name = "kuratowski_subgraph"><i>Kuratowski subgraph</i></a>. Because of
  79 the above theorem, given any graph, one can produce either a plane drawing of
  80 a graph, which will certify that the graph is planar, or a minimal set of edges
  81 that forms a Kuratowski subgraph, which will certify that the graph is
  82 non-planar - in both cases, the certificate of planarity or non-planarity is
  83 easy to check.
  84 <p>
  85 Any plane drawing separates the plane into distinct regions bordered by graph
  86 edges called <i>faces</i>. As a simple example, any embedding of a triangle
  87 into the plane separates it into two faces: the region inside the triangle and
  88 the (unbounded) region outside the triangle. The unbounded region outside the
  89 graph's embedding is called the <i>outer face</i>. Every embedding yields
  90 one outer face and zero or more inner faces. A famous result called
  91 Euler's formula states that for any
  92 planar graph with <i>n</i> vertices, <i>e</i> edges, <i>f</i> faces, and
  93 <i>c</i> connected components,
  94 <a name="EulersFormula">
  95 <blockquote>
  96 <i>n + f = e + c + 1</i>
  97 </blockquote>
  98 </a>
  99 This formula implies that any planar graph with no self-loops or parallel edges
 100 has at most <i>3n - 6</i> edges and <i>2n- 4</i> faces. Because of these
 101 bounds, algorithms on planar graphs can run in time <i>O(n)</i> or space
 102 <i>O(n)</i> on an <i>n</i> vertex graph even if they have to traverse all
 103 edges or faces of the graph.
 104 <p>
 105 A convenient way to separate the actual planarity test from algorithms that
 106 accept a planar graph as input is through an intermediate structure called a
 107 <i>planar embedding</i>. Instead of specifying the absolute positions of the
 108 vertices and edges in the plane as a plane drawing would, a planar embedding
 109 specifies their positions relative to one another. A planar embedding consists
 110 of a sequence, for each vertex in the graph, of all of the edges incident on
 111 that vertex in the order in which they are to be drawn around that vertex.
 112 The orderings defined by this sequence
 113 can either represent a clockwise or counter-clockwise iteration through the
 114 neighbors of each vertex, but the orientation must be
 115 consistent across the entire embedding.
 116 <p>
 117 In the Boost Graph Library, a planar embedding is a model of the
 118 <a href="./PlanarEmbedding.html">PlanarEmbedding</a> concept. A type that
 119 models PlanarEmbedding can be passed into the planarity test and populated if
 120 the input graph is planar. All other "back end" planar graph algorithms accept
 121 this populated PlanarEmbedding as an input. Conceptually, a type that models
 122 PlanarEmbedding is a <a href="../../property_map/doc/property_map.html">property
 123 map</a> that maps each vertex to a sequence of edges,
 124 where the sequence of edges has a similar interface to a standard C++
 125 container. The sequence of edges each vertex maps to represents the ordering
 126 of edges adjacent to that vertex. This interface is flexible enough to allow
 127 storage of the planar embedding independent from the graph in, say, a
 128 <tt>std::vector</tt> of <tt>std::vector</tt>s, or to allow for graph
 129 implementations that actually store lists of adjacent edges/vertices to
 130 internally re-arrange their storage to represent the planar embedding.
 131 Currently, only the former approach is supported when using the native graph
 132 types (<tt>adjacency_list</tt>, <tt>adjacency_matrix</tt>, etc.)
 133 of the Boost Graph Library.
 134
 135 <H3>Tools for working with planar graphs in the Boost Graph Library</h3>
 136
 137 The Boost Graph Library planar graph algorithms all work on undirected graphs.
 138 Some algorithms require certain degrees of connectivity of the input graph,
 139 but all algorithms work on graphs with self-loops and parallel edges.
 140 <p>
 141 The function <tt><a href = "boyer_myrvold.html">boyer_myrvold_planarity_test
 142 </a></tt> can be used to test whether or not a graph is planar, but it can also
 143 produce two important side-effects: in the case the graph is not planar, it can
 144 isolate a Kuratowski subgraph, and in the case the graph is planar, it can
 145 compute a planar embedding. The Boyer-Myrvold algorithm works on any undirected
 146  graph.
 147 <p>
 148 An undirected graph is <i>connected</i> if, for any two vertices <i>u</i> and
 149 <i>v</i>, there's a path from <i>u</i> to <i>v</i>. An undirected graph is
 150 <i>biconnected</i> if it is connected and it remains connected even if any
 151 single vertex is removed. Finally, a planar graph is
 152 <i>maximal planar</i> (also called
 153 <i>triangulated</i>) if no additional edge (with the exception of self-loops
 154 and parallel edges) can be added to it without creating
 155 a non-planar graph. Any maximal planar simple graph on <i>n > 2</i> vertices
 156 has exactly <i>3n - 6</i> edges and <i>2n - 4</i> faces, a consequence of
 157 Euler's formula. If a planar graph isn't connected, isn't biconnected, or isn't
 158 maximal planar, there is some set of edges that can be added to the graph to
 159 make it satisfy any of those three properties while preserving planarity. Many
 160 planar graph drawing algorithms make at least one of these three assumptions
 161 about the input graph, so there are functions in the Boost Graph Library that
 162 can help:
 163 <ul>
 164 <li><tt><a href="make_connected.html">make_connected</a></tt> adds a minimal
 165 set of edges to an undirected graph to make it connected.
 166 <li><tt><a href="make_biconnected_planar.html">make_biconnected_planar</a></tt>
 167 adds a set of edges to a connected, undirected planar graph to make it
 168 biconnected while preserving planarity.
 169 <li><tt><a href="make_maximal_planar.html">make_maximal_planar</a></tt> adds a
 170 set of edges to a biconnected, undirected planar graph to make it maximal
 171 planar.
 172 </ul>
 173 <p>
 174 Some algorithms involve a traversal of the faces of the graph, and the Boost
 175 Graph Library has the generic traversal function
 176 <tt><a href="planar_face_traversal.html">planar_face_traversal</a></tt> for
 177 this purpose. This traversal, like other traversals in the Boost Graph Library,
 178 can be customized by overriding event points in an appropriately defined
 179 <a href="PlanarFaceVisitor.html">visitor class</a>.
 180 <p>
 181 An intermediate step in some drawing algorithms for planar graphs is the
 182 creation of
 183 a <i>canonical ordering</i> of the vertices. A canonical ordering is a
 184 permutation of the vertices of a maximal planar graph. It orders the vertices
 185 in a way that makes it straightforward to draw the <i>i</i>th vertex once the
 186 first <i>(i-1)</i> vertices have been drawn - the only edges connecting the
 187 <i>i</i>th vertex to vertices already drawn will be adjacent to a consecutive
 188 sequence of vertices along the outer face of the partially embedded graph. The
 189 function
 190 <tt><a href="planar_canonical_ordering.html">planar_canonical_ordering</a></tt>
 191 will create such an ordering, given a maximal planar graph and a planar
 192 embedding of that graph.
 193 <p>
 194 A straight line drawing can be created using the function
 195 <tt>
 196 <a href="straight_line_drawing.html">chrobak_payne_straight_line_drawing</a>,
 197 </tt> which takes a maximal planar graph, a planar embedding of that
 198 graph, and a canonical ordering as input. The resulting drawing maps all of the
 199 vertices from a graph with <i>n</i> vertices to integer coordinates on a
 200 <i>(2n-4) x (n-2)</i> grid such that when the edges of the graph are drawn
 201 as line segments connecting vertices, no two edges cross. Self-loops and
 202 parallel edges are ignored by this algorithm.
 203 <p>
 204 Finally, there are two functions that can be used to verify the results of the
 205 <tt>boyer_myrvold_planarity_test</tt> and
 206 <tt>chrobak_payne_straight_line_drawing</tt> functions:
 207 <ul>
 208 <li><tt><a href="is_kuratowski_subgraph.html">is_kuratowski_subgraph</a></tt>
 209 takes the output of <tt>boyer_myrvold_planarity_test</tt> on a nonplanar graph
 210 and verifies that it can be contracted into a graph isomorphic to a Kuratowski
 211 subgraph.
 212 <li><tt><a href="is_straight_line_drawing.html">is_straight_line_drawing</a>
 213 </tt> takes the output of <tt>chrobak_payne_straight_line_drawing</tt> and uses
 214 a planar sweep algorithm to verify that none of the embedded edges intersect.
 215 </ul>
 216
 217 <h3>Complexity</h3>
 218
 219 Most of the algorithms in the Boost Graph Library that deal with planar graphs
 220 run in time <i>O(n)</i> on an input graph with <i>n</i> vertices. This achieves
 221 a theoretically optimal bound (you must at least iterate over all <i>n</i>
 222 vertices in order to embed a graph in the plane.) However, some of the work
 223 that goes into achieving these theoretically optimal time bounds may come at
 224 the expense of practical performance. For example, since any comparison-based
 225 sorting algorithm uses at least on the order of <i>n log n</i> comparisons in
 226 the worst case, any time an algorithm dealing with planar graphs needs to sort,
 227 a bucket sort is used to sort in <i>O(n)</i> time. Also, computing a planar
 228 embedding of a graph involves maintaining an ordered list of edges around a
 229 vertex, and this list of edges needs to support an arbitrary sequence of
 230 concatenations and reversals. A <tt>std::list</tt> can only guarantee
 231 <i>O(n<sup>2</sup>)</i> for a mixed sequence of <i>n</i> concatenations and
 232 reversals (since <tt>reverse</tt> is an <i>O(n)</i> operation.) However, our
 233 implementation achieves <i>O(n)</i> for these operations by using a list data
 234 structure that implements mixed sequences of concatenations and reversals
 235 lazily.
 236 <p>
 237 In both of the above cases, it may be preferable to sacrifice the nice
 238 theoretical upper bound for performance by using the C++ STL. The bucket sort
 239 allocates and populates a vector of vectors; because of the overhead in
 240 doing so, <tt>std::stable_sort</tt> may actually be faster in some cases.
 241 The custom list also uses more space than <tt>std::list</tt>, and it's not
 242 clear that anything other than carefully constructed pathological examples
 243 could force a <tt>std::list</tt> to use <i>n<sup>2</sup></i> operations within
 244 the planar embedding algorithm. For these reasons, the macro
 245 <tt>BOOST_GRAPH_PREFER_STD_LIB</tt> exists, which, when defined, will force
 246 the planar graph algorithms to use <tt>std::stable_sort</tt> and
 247 <tt>std::list</tt> in the examples above.
 248 <p>
 249 See the documentation on individual algorithms for more information about
 250 complexity guarantees.
 251
 252
 253 <h3>Examples</h3>
 254
 255 <ol>
 256 <li><a href="../example/simple_planarity_test.cpp">Testing whether or not a
 257 graph is planar.</a>
 258 <li><a href="../example/straight_line_drawing.cpp">Creating a straight line
 259 drawing of a graph in the plane.</a>
 260 </ol>
 261
 262 <h3>Notes</h3>
 263
 264 <p><a name="1">[1]</a> A graph <i>G'</i> is an expansion of a graph <i>G</i> if
 265 <i>G'</i> can be created from <i>G</i> by a series of zero or more <i>edge
 266 subdivisions</i>: take any edge <i>{x,y}</i> in the graph, remove it, add a new
 267 vertex <i>z</i>, and add the two edges <i>{x,z}</i> and <i>{z,y}</i> to the
 268 graph. For example, a path of any length is an expansion of a single edge and
 269 a cycle of any length is an expansion of a triangle.
 270
 271 <br>
 272 <HR>
 273 Copyright &copy; 2007 Aaron Windsor (<a href="mailto:aaron.windsor@gmail.com">
 274 aaron.windsor@gmail.com</a>)
 275 </BODY>
 276 </HTML>