260 lines
11 KiB
HTML
260 lines
11 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: Boyer-Myrvold Planarity Testing/Embedding</Title>
|
|
<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>Boyer-Myrvold Planarity Testing/Embedding</H1>
|
|
|
|
<p>
|
|
A graph is <a href="./planar_graphs.html#planar"><i>planar</i></a> if it can
|
|
be drawn in two-dimensional space without any of its edges crossing. Such a
|
|
drawing of a planar graph is called a
|
|
<a href="./planar_graphs.html#plane_drawing"><i>plane drawing</i></a>. Each
|
|
plane drawing belongs to an equivalence class called a <i>planar embedding</i>
|
|
<a href="#1">[1]</a> that is defined by the clockwise ordering of adjacent
|
|
edges around each vertex in the graph. A planar embedding is a convenient
|
|
intermediate representation of an actual drawing of a planar graph, and many
|
|
planar graph drawing algorithms are formulated as functions mapping a planar
|
|
embedding to a plane drawing.
|
|
<br>
|
|
<br>
|
|
<table align="center" class="image">
|
|
<caption align="bottom"><h5>A planar graph (top left), along with a planar
|
|
embedding of that graph (bottom left) can be used to create a plane drawing
|
|
(right) by embedding edges around each vertex in the order in which they
|
|
appear in the planar embedding.
|
|
</h5></caption>
|
|
<tr><td>
|
|
<img src="./figs/embedding_illustration.png">
|
|
</td></tr>
|
|
<tr></tr>
|
|
<tr></tr>
|
|
</table>
|
|
<br>
|
|
<p>
|
|
The function <tt>boyer_myrvold_planarity_test</tt> implements the planarity
|
|
testing/embedding algorithm of Boyer and Myrvold
|
|
[<a href="./bibliography.html#boyermyrvold04">70</a>].
|
|
<tt>boyer_myrvold_planarity_test</tt> returns <tt>true</tt> if the input graph
|
|
is planar and <tt>false</tt> otherwise. As a side-effect of this test, a planar
|
|
embedding can be constructed if the graph is planar or a minimal set of edges
|
|
that form a <a href = "./planar_graphs.html#kuratowskisubgraphs">Kuratowski
|
|
subgraph</a> can be found if the graph is not planar.
|
|
<tt>boyer_myrvold_planarity_test</tt> uses named parameter arguments (courtesy
|
|
of the <a href="../../parameter/doc/html/index.html">Boost.Parameter</a>
|
|
library) to specify what the function actually does. Some examples are:
|
|
|
|
<ul>
|
|
<li>Testing whether or not a graph is planar:
|
|
<pre>
|
|
bool is_planar = boyer_myrvold_planarity_test(g);
|
|
</pre>
|
|
|
|
<li>Computing a planar embedding for a graph if it is planar, otherwise finding
|
|
a set of edges that forms an obstructing Kuratowski subgraph:
|
|
<pre>
|
|
if (boyer_myrvold_planarity_test(boyer_myrvold_params::graph = g,
|
|
boyer_myrvold_params::embedding = embedding_pmap,
|
|
boyer_myrvold_params::kuratowski_subgraph = out_itr
|
|
)
|
|
)
|
|
{
|
|
//do something with the embedding in embedding_pmap
|
|
}
|
|
else
|
|
{
|
|
//do something with the kuratowski subgraph output to out_itr
|
|
}
|
|
</pre>
|
|
</ul>
|
|
|
|
<p>
|
|
The parameters passed to <tt>boyer_myrvold_planarity_test</tt> in the examples
|
|
above do more than just carry the data structures used for input and output -
|
|
the algorithm is optimized at compile time based on which parameters are
|
|
present. A complete list of parameters accepted and their interactions are
|
|
described below.
|
|
<p>
|
|
<tt>boyer_myrvold_planarity_test</tt> accepts as input any undirected graph,
|
|
even those with self-loops and multiple edges.
|
|
However, many planar graph drawing algorithms make additional restrictions
|
|
on the structure of the input graph - for example, requiring that the input
|
|
graph is connected, biconnected, or even maximal planar (triangulated.)
|
|
Fortunately, any planar graph on <i>n</i> vertices that lacks one of these
|
|
properties can be augmented with additional edges so that it satisfies that
|
|
property in <i>O(n)</i> time - the functions
|
|
<tt><a href="./make_connected.html">make_connected</a></tt>,
|
|
<tt><a href="./make_biconnected_planar.html">make_biconnected_planar</a></tt>,
|
|
and <tt><a href="./make_maximal_planar.html">make_maximal_planar</a></tt>
|
|
exist for this purpose. If the graph drawing algorithm you're using requires,
|
|
say, a biconnected graph, then you must make your input graph biconnected
|
|
<i>before</i> passing it into <tt>boyer_myrvold_planarity_test</tt> so that the
|
|
computed planar embedding includes these additional edges. This may require
|
|
more than one call to <tt>boyer_myrvold_planarity_test</tt> depending on the
|
|
structure of the graph you begin with, since both
|
|
<tt>make_biconnected_planar</tt> and <tt>make_maximal_planar</tt> require a
|
|
planar embedding of the existing graph as an input parameter.
|
|
|
|
<p><p>
|
|
The named parameters accepted by <tt>boyer_myrvold_planarity_test</tt> are:
|
|
|
|
<ul>
|
|
<li><b><tt>graph</tt></b> : The input graph - this is the only required
|
|
parameter.
|
|
<li><b><tt>vertex_index_map</tt></b> : A mapping from vertices of the input
|
|
graph to indexes in the range <tt>[0..num_vertices(g))</tt>. If this parameter
|
|
is not provided, the vertex index map is assumed to be available as an interior
|
|
property of the graph, accessible by calling <tt>get(vertex_index, g)</tt>.
|
|
<li><b><tt>edge_index_map</tt></b>: A mapping from the edges of the input graph
|
|
to indexes in the range <tt>[0..num_edges(g))</tt>. This parameter is only
|
|
needed if the <tt>kuratowski_subgraph</tt> argument is provided. If the
|
|
<tt>kuratowski_subgraph</tt> argument is provided and this parameter is not
|
|
provided, the EdgeIndexMap is assumed to be available as an interior property
|
|
accessible by calling <tt>get(edge_index, g)</tt>.
|
|
<li><b><tt>embedding</tt></b> : If the graph is planar, this will be populated
|
|
with a mapping from vertices to the clockwise order of neighbors in the planar
|
|
embedding.
|
|
<li><b><tt>kuratowski_subgraph</tt></b> : If the graph is not planar, a minimal
|
|
set of edges that form the obstructing Kuratowski subgraph will be written to
|
|
this iterator.
|
|
</ul>
|
|
|
|
These named parameters all belong to the namespace
|
|
<tt>boyer_myrvold_params</tt>. See below for more information on the concepts
|
|
required for these arguments.
|
|
|
|
<H3>Verifying the output</H3>
|
|
|
|
Whether or not the input graph is planar, <tt>boyer_myrvold_planarity_test</tt>
|
|
can produce a certificate that can be automatically checked to verify that the
|
|
function is working properly.
|
|
<p>
|
|
If the graph is planar, a planar embedding can be produced. The
|
|
planar embedding can be verified by passing it to a plane drawing routine
|
|
(such as <tt><a href="straight_line_drawing.html">
|
|
chrobak_payne_straight_line_drawing</a></tt>) and using the function
|
|
<tt><a href="is_straight_line_drawing.html">is_straight_line_drawing</a></tt>
|
|
to verify that the resulting graph is planar.
|
|
<p>
|
|
If the graph is not planar, a set of edges that forms a Kuratowski subgraph in
|
|
the original graph can be produced. This set of edges can be passed to the
|
|
function <tt><a href="is_kuratowski_subgraph.html">is_kuratowski_subgraph</a>
|
|
</tt> to verify that they can be contracted into a <i>K<sub>5</sub></i> or
|
|
<i>K<sub>3,3</sub></i>. <tt>boyer_myrvold_planarity_test</tt> chooses the set
|
|
of edges forming the Kuratowski subgraph in such a way that the contraction to
|
|
a <i>K<sub>5</sub></i> or <i>K<sub>3,3</sub></i> can be done by a simple
|
|
deterministic process which is described in the documentation to
|
|
<tt>is_kuratowski_subgraph</tt>.
|
|
|
|
<H3>Where Defined</H3>
|
|
|
|
<P>
|
|
<a href="../../../boost/graph/boyer_myrvold_planar_test.hpp">
|
|
<TT>boost/graph/boyer_myrvold_planar_test.hpp</TT>
|
|
</a>
|
|
|
|
<H3>Parameters</H3>
|
|
|
|
IN: <tt>Graph& g</tt>
|
|
|
|
<blockquote>
|
|
Any undirected graph. The graph type must be a model of
|
|
<a href="VertexAndEdgeListGraph.html">VertexAndEdgeListGraph</a> and
|
|
<a href="IncidenceGraph.html">IncidenceGraph</a>.
|
|
</blockquote>
|
|
|
|
OUT <tt>PlanarEmbedding embedding</tt>
|
|
|
|
<blockquote>
|
|
Must model the <a href="PlanarEmbedding.html">PlanarEmbedding</a> concept.
|
|
</blockquote>
|
|
|
|
IN <tt>OutputIterator kuratowski_subgraph</tt>
|
|
|
|
<blockquote>
|
|
An OutputIterator which accepts values of the type
|
|
<tt>graph_traits<Graph>::edge_descriptor</tt>
|
|
</blockquote>
|
|
|
|
IN <tt>VertexIndexMap vm</tt>
|
|
|
|
<blockquote>
|
|
A <a href="../../property_map/doc/ReadablePropertyMap.html">Readable Property Map
|
|
</a> that maps vertices from <tt>g</tt> to distinct integers in the range
|
|
<tt>[0, num_vertices(g) )</tt><br>
|
|
<b>Default</b>: <tt>get(vertex_index,g)</tt><br>
|
|
</blockquote>
|
|
|
|
IN <tt>EdgeIndexMap em</tt>
|
|
|
|
<blockquote>
|
|
A <a href="../../property_map/doc/ReadablePropertyMap.html">Readable Property Map
|
|
</a> that maps edges from <tt>g</tt> to distinct integers in the range
|
|
<tt>[0, num_edges(g) )</tt><br>
|
|
<b>Default</b>: <tt>get(edge_index,g)</tt>, but this parameter is only used if
|
|
the <tt>kuratowski_subgraph_iterator</tt> is provided.<br>
|
|
</blockquote>
|
|
|
|
<H3>Complexity</H3>
|
|
|
|
Assuming that both the vertex index and edge index supplied take time
|
|
<i>O(1)</i> to return an index and there are <i>O(n)</i>
|
|
total self-loops and parallel edges in the graph, most combinations of
|
|
arguments given to
|
|
<tt>boyer_myrvold_planarity_test</tt> result in an algorithm that runs in time
|
|
<i>O(n)</i> for a graph with <i>n</i> vertices and <i>m</i> edges. The only
|
|
exception is when Kuratowski subgraph isolation is requested for a dense graph
|
|
(a graph with <i>n = o(m)</i>) - the running time will be <i>O(n+m)</i>
|
|
<a href = "#2">[2]</a>.
|
|
|
|
<H3>Examples</H3>
|
|
|
|
<P>
|
|
<ul>
|
|
<li><a href="../example/simple_planarity_test.cpp">A simple planarity test</a>
|
|
<li><a href="../example/kuratowski_subgraph.cpp">Isolating a Kuratowski
|
|
Subgraph</a>
|
|
<li><a href="../example/straight_line_drawing.cpp">Using a planar embedding to
|
|
create a straight line drawing</a>
|
|
</ul>
|
|
|
|
<h3>See Also</h3>
|
|
|
|
<a href="./planar_graphs.html">Planar Graphs in the Boost Graph Library</a>
|
|
|
|
|
|
<h3>Notes</h3>
|
|
|
|
<p><a name="1">[1] A planar embedding is also called a <i>combinatorial
|
|
embedding</i>.
|
|
|
|
<p><a name="2">[2] The algorithm can still be made to run in time <i>O(n)</i>
|
|
for this case, if needed. <a href="planar_graphs.html#EulersFormula">Euler's
|
|
formula</a> implies that a planar graph with <i>n</i> vertices can have no more
|
|
than <i>3n - 6</i> edges, which means that any non-planar graph on <i>n</i>
|
|
vertices has a subgraph of only <i>3n - 5</i> edges that contains a Kuratowski
|
|
subgraph. So, if you need to find a Kuratowski subgraph of a graph with more
|
|
than <i>3n - 5</i> edges in time <i>O(n)</i>, you can create a subgraph of the
|
|
original graph consisting of any arbitrary <i>3n - 5</i> edges and pass that
|
|
graph to <tt>boyer_myrvold_planarity_test</tt>.
|
|
|
|
|
|
<br>
|
|
<HR>
|
|
Copyright © 2007 Aaron Windsor (<a href="mailto:aaron.windsor@gmail.com">
|
|
aaron.windsor@gmail.com</a>)
|
|
</BODY>
|
|
</HTML>
|