123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276 |
- <HTML>
- <!-- Copyright 2007 Aaron Windsor
-
- Distributed under the Boost Software License, Version 1.0.
- (See accompanying file LICENSE_1_0.txt or copy at
- http://www.boost.org/LICENSE_1_0.txt)
-
- -->
- <HEAD>
- <TITLE>Boost Graph Library: Planar Graphs</TITLE>
- </HEAD>
- <BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
- ALINK="#ff0000">
- <IMG SRC="../../../boost.png"
- ALT="C++ Boost" width="277" height="86">
- <BR Clear>
- <H1>Planar Graphs</H1>
- <p>
- A graph is <a name="planar"><i>planar</i></a> if it can be drawn in
- two-dimensional space with no two of its edges crossing. Such a drawing of a
- planar graph is called a <a name="plane_drawing"><i>plane drawing</i></a>.
- Every planar graph also admits a <i>straight-line drawing</i>, which is a
- plane drawing where each edge is represented by a line segment.
- <br>
- <br>
- <table class="image" align="center">
- <caption align="bottom">
- <h5>A planar graph (left), a plane drawing (center), and a straight line
- drawing (right), all of the same graph</h5>
- </caption>
- <tr>
- <td>
- <img src="./figs/planar_plane_straight_line.png">
- </td>
- </tr>
- <tr></tr>
- <table>
- <br>
- Two examples of non-planar graphs are K<sub>5</sub>, the complete graph on
- five vertices, and K<sub>3,3</sub>, the complete bipartite graph on six
- vertices with three vertices in each bipartition. No matter how the vertices
- of either graph are arranged in the plane, at least two edges are forced to
- cross.
- <a name = "kuratowskisubgraphs">
- <br>
- <br>
- <table class="image" align="center">
- <caption align="bottom"><h5>K<sub>5</sub> (left) and K<sub>3,3</sub> (right) -
- the two Kuratowski subgraphs</h5>
- </caption>
- <tr>
- <td>
- <img src="./figs/k_5_and_k_3_3.png">
- </td>
- </tr>
- </table>
- <br>
- The above graphs are both minimal examples of non-planarity within
- their class of graphs; delete any edge or vertex from either one and the
- resulting graph is planar. A theorem of Kuratowski singles these two graphs
- out as fundamental obstructions to planarity within any graph:
- <blockquote>
- <i>
- A graph is planar if and only if it does not contain a subgraph that is an
- expansion<a href="#1">[1]</a> of either K<sub>5</sub> or K<sub>3,3</sub>
- </i>
- </blockquote>
- <p>
- A subgraph that is an expansion of K<sub>5</sub> or K<sub>3,3</sub> is called
- a <a name = "kuratowski_subgraph"><i>Kuratowski subgraph</i></a>. Because of
- the above theorem, given any graph, one can produce either a plane drawing of
- a graph, which will certify that the graph is planar, or a minimal set of edges
- that forms a Kuratowski subgraph, which will certify that the graph is
- non-planar - in both cases, the certificate of planarity or non-planarity is
- easy to check.
- <p>
- Any plane drawing separates the plane into distinct regions bordered by graph
- edges called <i>faces</i>. As a simple example, any embedding of a triangle
- into the plane separates it into two faces: the region inside the triangle and
- the (unbounded) region outside the triangle. The unbounded region outside the
- graph's embedding is called the <i>outer face</i>. Every embedding yields
- one outer face and zero or more inner faces. A famous result called
- Euler's formula states that for any
- planar graph with <i>n</i> vertices, <i>e</i> edges, <i>f</i> faces, and
- <i>c</i> connected components,
- <a name="EulersFormula">
- <blockquote>
- <i>n + f = e + c + 1</i>
- </blockquote>
- </a>
- This formula implies that any planar graph with no self-loops or parallel edges
- has at most <i>3n - 6</i> edges and <i>2n- 4</i> faces. Because of these
- bounds, algorithms on planar graphs can run in time <i>O(n)</i> or space
- <i>O(n)</i> on an <i>n</i> vertex graph even if they have to traverse all
- edges or faces of the graph.
- <p>
- A convenient way to separate the actual planarity test from algorithms that
- accept a planar graph as input is through an intermediate structure called a
- <i>planar embedding</i>. Instead of specifying the absolute positions of the
- vertices and edges in the plane as a plane drawing would, a planar embedding
- specifies their positions relative to one another. A planar embedding consists
- of a sequence, for each vertex in the graph, of all of the edges incident on
- that vertex in the order in which they are to be drawn around that vertex.
- The orderings defined by this sequence
- can either represent a clockwise or counter-clockwise iteration through the
- neighbors of each vertex, but the orientation must be
- consistent across the entire embedding.
- <p>
- In the Boost Graph Library, a planar embedding is a model of the
- <a href="./PlanarEmbedding.html">PlanarEmbedding</a> concept. A type that
- models PlanarEmbedding can be passed into the planarity test and populated if
- the input graph is planar. All other "back end" planar graph algorithms accept
- this populated PlanarEmbedding as an input. Conceptually, a type that models
- PlanarEmbedding is a <a href="../../property_map/doc/property_map.html">property
- map</a> that maps each vertex to a sequence of edges,
- where the sequence of edges has a similar interface to a standard C++
- container. The sequence of edges each vertex maps to represents the ordering
- of edges adjacent to that vertex. This interface is flexible enough to allow
- storage of the planar embedding independent from the graph in, say, a
- <tt>std::vector</tt> of <tt>std::vector</tt>s, or to allow for graph
- implementations that actually store lists of adjacent edges/vertices to
- internally re-arrange their storage to represent the planar embedding.
- Currently, only the former approach is supported when using the native graph
- types (<tt>adjacency_list</tt>, <tt>adjacency_matrix</tt>, etc.)
- of the Boost Graph Library.
- <H3>Tools for working with planar graphs in the Boost Graph Library</h3>
- The Boost Graph Library planar graph algorithms all work on undirected graphs.
- Some algorithms require certain degrees of connectivity of the input graph,
- but all algorithms work on graphs with self-loops and parallel edges.
- <p>
- The function <tt><a href = "boyer_myrvold.html">boyer_myrvold_planarity_test
- </a></tt> can be used to test whether or not a graph is planar, but it can also
- produce two important side-effects: in the case the graph is not planar, it can
- isolate a Kuratowski subgraph, and in the case the graph is planar, it can
- compute a planar embedding. The Boyer-Myrvold algorithm works on any undirected
- graph.
- <p>
- An undirected graph is <i>connected</i> if, for any two vertices <i>u</i> and
- <i>v</i>, there's a path from <i>u</i> to <i>v</i>. An undirected graph is
- <i>biconnected</i> if it is connected and it remains connected even if any
- single vertex is removed. Finally, a planar graph is
- <i>maximal planar</i> (also called
- <i>triangulated</i>) if no additional edge (with the exception of self-loops
- and parallel edges) can be added to it without creating
- a non-planar graph. Any maximal planar simple graph on <i>n > 2</i> vertices
- has exactly <i>3n - 6</i> edges and <i>2n - 4</i> faces, a consequence of
- Euler's formula. If a planar graph isn't connected, isn't biconnected, or isn't
- maximal planar, there is some set of edges that can be added to the graph to
- make it satisfy any of those three properties while preserving planarity. Many
- planar graph drawing algorithms make at least one of these three assumptions
- about the input graph, so there are functions in the Boost Graph Library that
- can help:
- <ul>
- <li><tt><a href="make_connected.html">make_connected</a></tt> adds a minimal
- set of edges to an undirected graph to make it connected.
- <li><tt><a href="make_biconnected_planar.html">make_biconnected_planar</a></tt>
- adds a set of edges to a connected, undirected planar graph to make it
- biconnected while preserving planarity.
- <li><tt><a href="make_maximal_planar.html">make_maximal_planar</a></tt> adds a
- set of edges to a biconnected, undirected planar graph to make it maximal
- planar.
- </ul>
- <p>
- Some algorithms involve a traversal of the faces of the graph, and the Boost
- Graph Library has the generic traversal function
- <tt><a href="planar_face_traversal.html">planar_face_traversal</a></tt> for
- this purpose. This traversal, like other traversals in the Boost Graph Library,
- can be customized by overriding event points in an appropriately defined
- <a href="PlanarFaceVisitor.html">visitor class</a>.
- <p>
- An intermediate step in some drawing algorithms for planar graphs is the
- creation of
- a <i>canonical ordering</i> of the vertices. A canonical ordering is a
- permutation of the vertices of a maximal planar graph. It orders the vertices
- in a way that makes it straightforward to draw the <i>i</i>th vertex once the
- first <i>(i-1)</i> vertices have been drawn - the only edges connecting the
- <i>i</i>th vertex to vertices already drawn will be adjacent to a consecutive
- sequence of vertices along the outer face of the partially embedded graph. The
- function
- <tt><a href="planar_canonical_ordering.html">planar_canonical_ordering</a></tt>
- will create such an ordering, given a maximal planar graph and a planar
- embedding of that graph.
- <p>
- A straight line drawing can be created using the function
- <tt>
- <a href="straight_line_drawing.html">chrobak_payne_straight_line_drawing</a>,
- </tt> which takes a maximal planar graph, a planar embedding of that
- graph, and a canonical ordering as input. The resulting drawing maps all of the
- vertices from a graph with <i>n</i> vertices to integer coordinates on a
- <i>(2n-4) x (n-2)</i> grid such that when the edges of the graph are drawn
- as line segments connecting vertices, no two edges cross. Self-loops and
- parallel edges are ignored by this algorithm.
- <p>
- Finally, there are two functions that can be used to verify the results of the
- <tt>boyer_myrvold_planarity_test</tt> and
- <tt>chrobak_payne_straight_line_drawing</tt> functions:
- <ul>
- <li><tt><a href="is_kuratowski_subgraph.html">is_kuratowski_subgraph</a></tt>
- takes the output of <tt>boyer_myrvold_planarity_test</tt> on a nonplanar graph
- and verifies that it can be contracted into a graph isomorphic to a Kuratowski
- subgraph.
- <li><tt><a href="is_straight_line_drawing.html">is_straight_line_drawing</a>
- </tt> takes the output of <tt>chrobak_payne_straight_line_drawing</tt> and uses
- a planar sweep algorithm to verify that none of the embedded edges intersect.
- </ul>
- <h3>Complexity</h3>
- Most of the algorithms in the Boost Graph Library that deal with planar graphs
- run in time <i>O(n)</i> on an input graph with <i>n</i> vertices. This achieves
- a theoretically optimal bound (you must at least iterate over all <i>n</i>
- vertices in order to embed a graph in the plane.) However, some of the work
- that goes into achieving these theoretically optimal time bounds may come at
- the expense of practical performance. For example, since any comparison-based
- sorting algorithm uses at least on the order of <i>n log n</i> comparisons in
- the worst case, any time an algorithm dealing with planar graphs needs to sort,
- a bucket sort is used to sort in <i>O(n)</i> time. Also, computing a planar
- embedding of a graph involves maintaining an ordered list of edges around a
- vertex, and this list of edges needs to support an arbitrary sequence of
- concatenations and reversals. A <tt>std::list</tt> can only guarantee
- <i>O(n<sup>2</sup>)</i> for a mixed sequence of <i>n</i> concatenations and
- reversals (since <tt>reverse</tt> is an <i>O(n)</i> operation.) However, our
- implementation achieves <i>O(n)</i> for these operations by using a list data
- structure that implements mixed sequences of concatenations and reversals
- lazily.
- <p>
- In both of the above cases, it may be preferable to sacrifice the nice
- theoretical upper bound for performance by using the C++ STL. The bucket sort
- allocates and populates a vector of vectors; because of the overhead in
- doing so, <tt>std::stable_sort</tt> may actually be faster in some cases.
- The custom list also uses more space than <tt>std::list</tt>, and it's not
- clear that anything other than carefully constructed pathological examples
- could force a <tt>std::list</tt> to use <i>n<sup>2</sup></i> operations within
- the planar embedding algorithm. For these reasons, the macro
- <tt>BOOST_GRAPH_PREFER_STD_LIB</tt> exists, which, when defined, will force
- the planar graph algorithms to use <tt>std::stable_sort</tt> and
- <tt>std::list</tt> in the examples above.
- <p>
- See the documentation on individual algorithms for more information about
- complexity guarantees.
- <h3>Examples</h3>
- <ol>
- <li><a href="../example/simple_planarity_test.cpp">Testing whether or not a
- graph is planar.</a>
- <li><a href="../example/straight_line_drawing.cpp">Creating a straight line
- drawing of a graph in the plane.</a>
- </ol>
- <h3>Notes</h3>
- <p><a name="1">[1]</a> A graph <i>G'</i> is an expansion of a graph <i>G</i> if
- <i>G'</i> can be created from <i>G</i> by a series of zero or more <i>edge
- subdivisions</i>: take any edge <i>{x,y}</i> in the graph, remove it, add a new
- vertex <i>z</i>, and add the two edges <i>{x,z}</i> and <i>{z,y}</i> to the
- graph. For example, a path of any length is an expansion of a single edge and
- a cycle of any length is an expansion of a triangle.
- <br>
- <HR>
- Copyright © 2007 Aaron Windsor (<a href="mailto:aaron.windsor@gmail.com">
- aaron.windsor@gmail.com</a>)
- </BODY>
- </HTML>
|