1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
|
<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/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/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>
|
