277 lines
13 KiB
HTML
277 lines
13 KiB
HTML
<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>
|