[ceph.git] / ceph / src / boost / libs / graph / doc / boyer_myrvold.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&amp; 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&lt;Graph&gt;::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 &copy; 2007 Aaron Windsor (<a href="mailto:aaron.windsor@gmail.com">
aaron.windsor@gmail.com</a>)
</BODY>
</HTML>
Commit	Line	Data
7c673cae FG	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: Boyer-Myrvold Planarity Testing/Embedding</Title>
	11	<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
	12	ALINK="#ff0000">
	13	<IMG SRC="../../../boost.png"
	14	ALT="C++ Boost" width="277" height="86">
	15
	16	<BR Clear>
	17
	18	<H1>Boyer-Myrvold Planarity Testing/Embedding</H1>
	19
	20	<p>
	21	A graph is <a href="./planar_graphs.html#planar"><i>planar</i></a> if it can
	22	be drawn in two-dimensional space without any of its edges crossing. Such a
	23	drawing of a planar graph is called a
	24	<a href="./planar_graphs.html#plane_drawing"><i>plane drawing</i></a>. Each
	25	plane drawing belongs to an equivalence class called a <i>planar embedding</i>
	26	<a href="#1">[1]</a> that is defined by the clockwise ordering of adjacent
	27	edges around each vertex in the graph. A planar embedding is a convenient
	28	intermediate representation of an actual drawing of a planar graph, and many
	29	planar graph drawing algorithms are formulated as functions mapping a planar
	30	embedding to a plane drawing.
	31	<br>
	32	<br>
	33	<table align="center" class="image">
	34	<caption align="bottom"><h5>A planar graph (top left), along with a planar
	35	embedding of that graph (bottom left) can be used to create a plane drawing
	36	(right) by embedding edges around each vertex in the order in which they
	37	appear in the planar embedding.
	38	</h5></caption>
	39	<tr><td>
	40	<img src="./figs/embedding_illustration.png">
	41	</td></tr>
	42	<tr></tr>
	43	<tr></tr>
	44	</table>
	45	<br>
	46	<p>
	47	The function <tt>boyer_myrvold_planarity_test</tt> implements the planarity
	48	testing/embedding algorithm of Boyer and Myrvold
	49	[<a href="./bibliography.html#boyermyrvold04">70</a>].
	50	<tt>boyer_myrvold_planarity_test</tt> returns <tt>true</tt> if the input graph
	51	is planar and <tt>false</tt> otherwise. As a side-effect of this test, a planar
	52	embedding can be constructed if the graph is planar or a minimal set of edges
	53	that form a <a href = "./planar_graphs.html#kuratowskisubgraphs">Kuratowski
	54	subgraph</a> can be found if the graph is not planar.
	55	<tt>boyer_myrvold_planarity_test</tt> uses named parameter arguments (courtesy
	56	of the <a href="../../parameter/doc/html/index.html">Boost.Parameter</a>
	57	library) to specify what the function actually does. Some examples are:
	58
	59	<ul>
	60	<li>Testing whether or not a graph is planar:
	61	<pre>
	62	bool is_planar = boyer_myrvold_planarity_test(g);
	63	</pre>
	64
65	<li>Computing a planar embedding for a graph if it is planar, otherwise finding
66	a set of edges that forms an obstructing Kuratowski subgraph:
67	<pre>
68	if (boyer_myrvold_planarity_test(boyer_myrvold_params::graph = g,
69	boyer_myrvold_params::embedding = embedding_pmap,
70	boyer_myrvold_params::kuratowski_subgraph = out_itr
71	)
72	)
73	{
74	//do something with the embedding in embedding_pmap
75	}
76	else
77	{
78	//do something with the kuratowski subgraph output to out_itr
79	}
80	</pre>
81	</ul>
82
83	<p>
84	The parameters passed to <tt>boyer_myrvold_planarity_test</tt> in the examples
85	above do more than just carry the data structures used for input and output -
86	the algorithm is optimized at compile time based on which parameters are
87	present. A complete list of parameters accepted and their interactions are
88	described below.
89	<p>
90	<tt>boyer_myrvold_planarity_test</tt> accepts as input any undirected graph,
91	even those with self-loops and multiple edges.
92	However, many planar graph drawing algorithms make additional restrictions
93	on the structure of the input graph - for example, requiring that the input
94	graph is connected, biconnected, or even maximal planar (triangulated.)
95	Fortunately, any planar graph on <i>n</i> vertices that lacks one of these
96	properties can be augmented with additional edges so that it satisfies that
97	property in <i>O(n)</i> time - the functions
98	<tt><a href="./make_connected.html">make_connected</a></tt>,
99	<tt><a href="./make_biconnected_planar.html">make_biconnected_planar</a></tt>,
100	and <tt><a href="./make_maximal_planar.html">make_maximal_planar</a></tt>
101	exist for this purpose. If the graph drawing algorithm you're using requires,
102	say, a biconnected graph, then you must make your input graph biconnected
103	<i>before</i> passing it into <tt>boyer_myrvold_planarity_test</tt> so that the
104	computed planar embedding includes these additional edges. This may require
105	more than one call to <tt>boyer_myrvold_planarity_test</tt> depending on the
106	structure of the graph you begin with, since both
107	<tt>make_biconnected_planar</tt> and <tt>make_maximal_planar</tt> require a
108	planar embedding of the existing graph as an input parameter.
109
110	<p><p>
111	The named parameters accepted by <tt>boyer_myrvold_planarity_test</tt> are:
112
113	<ul>
114	<li><b><tt>graph</tt></b> : The input graph - this is the only required
115	parameter.
116	<li><b><tt>vertex_index_map</tt></b> : A mapping from vertices of the input
117	graph to indexes in the range <tt>[0..num_vertices(g))</tt>. If this parameter
118	is not provided, the vertex index map is assumed to be available as an interior
119	property of the graph, accessible by calling <tt>get(vertex_index, g)</tt>.
120	<li><b><tt>edge_index_map</tt></b>: A mapping from the edges of the input graph
121	to indexes in the range <tt>[0..num_edges(g))</tt>. This parameter is only
122	needed if the <tt>kuratowski_subgraph</tt> argument is provided. If the
123	<tt>kuratowski_subgraph</tt> argument is provided and this parameter is not
124	provided, the EdgeIndexMap is assumed to be available as an interior property
125	accessible by calling <tt>get(edge_index, g)</tt>.
126	<li><b><tt>embedding</tt></b> : If the graph is planar, this will be populated
127	with a mapping from vertices to the clockwise order of neighbors in the planar
128	embedding.
129	<li><b><tt>kuratowski_subgraph</tt></b> : If the graph is not planar, a minimal
130	set of edges that form the obstructing Kuratowski subgraph will be written to
131	this iterator.
132	</ul>
133
134	These named parameters all belong to the namespace
135	<tt>boyer_myrvold_params</tt>. See below for more information on the concepts
136	required for these arguments.
137
138	<H3>Verifying the output</H3>
139
140	Whether or not the input graph is planar, <tt>boyer_myrvold_planarity_test</tt>
141	can produce a certificate that can be automatically checked to verify that the
142	function is working properly.
143	<p>
144	If the graph is planar, a planar embedding can be produced. The
145	planar embedding can be verified by passing it to a plane drawing routine
146	(such as <tt><a href="straight_line_drawing.html">
147	chrobak_payne_straight_line_drawing</a></tt>) and using the function
148	<tt><a href="is_straight_line_drawing.html">is_straight_line_drawing</a></tt>
149	to verify that the resulting graph is planar.
150	<p>
151	If the graph is not planar, a set of edges that forms a Kuratowski subgraph in
152	the original graph can be produced. This set of edges can be passed to the
153	function <tt><a href="is_kuratowski_subgraph.html">is_kuratowski_subgraph</a>
154	</tt> to verify that they can be contracted into a <i>K<sub>5</sub></i> or
155	<i>K<sub>3,3</sub></i>. <tt>boyer_myrvold_planarity_test</tt> chooses the set
156	of edges forming the Kuratowski subgraph in such a way that the contraction to
157	a <i>K<sub>5</sub></i> or <i>K<sub>3,3</sub></i> can be done by a simple
158	deterministic process which is described in the documentation to
159	<tt>is_kuratowski_subgraph</tt>.
160
161	<H3>Where Defined</H3>
162
163	<P>
164	<a href="../../../boost/graph/boyer_myrvold_planar_test.hpp">
165	<TT>boost/graph/boyer_myrvold_planar_test.hpp</TT>
166	</a>
167
168	<H3>Parameters</H3>
169
170	IN: <tt>Graph& g</tt>
171
172	<blockquote>
173	Any undirected graph. The graph type must be a model of
174	<a href="VertexAndEdgeListGraph.html">VertexAndEdgeListGraph</a> and
175	<a href="IncidenceGraph.html">IncidenceGraph</a>.
176	</blockquote>
177
178	OUT <tt>PlanarEmbedding embedding</tt>
179
180	<blockquote>
181	Must model the <a href="PlanarEmbedding.html">PlanarEmbedding</a> concept.
182	</blockquote>
183
184	IN <tt>OutputIterator kuratowski_subgraph</tt>
185
186	<blockquote>
187	An OutputIterator which accepts values of the type
188	<tt>graph_traits<Graph>::edge_descriptor</tt>
189	</blockquote>
190
191	IN <tt>VertexIndexMap vm</tt>
192
193	<blockquote>
194	A <a href="../../property_map/doc/ReadablePropertyMap.html">Readable Property Map
195	</a> that maps vertices from <tt>g</tt> to distinct integers in the range
196	<tt>[0, num_vertices(g) )</tt><br>
197	<b>Default</b>: <tt>get(vertex_index,g)</tt><br>
198	</blockquote>
199
200	IN <tt>EdgeIndexMap em</tt>
201
202	<blockquote>
203	A <a href="../../property_map/doc/ReadablePropertyMap.html">Readable Property Map
204	</a> that maps edges from <tt>g</tt> to distinct integers in the range
205	<tt>[0, num_edges(g) )</tt><br>
206	<b>Default</b>: <tt>get(edge_index,g)</tt>, but this parameter is only used if
207	the <tt>kuratowski_subgraph_iterator</tt> is provided.<br>
208	</blockquote>
209
210	<H3>Complexity</H3>
211
212	Assuming that both the vertex index and edge index supplied take time
213	<i>O(1)</i> to return an index and there are <i>O(n)</i>
214	total self-loops and parallel edges in the graph, most combinations of
215	arguments given to
216	<tt>boyer_myrvold_planarity_test</tt> result in an algorithm that runs in time
217	<i>O(n)</i> for a graph with <i>n</i> vertices and <i>m</i> edges. The only
218	exception is when Kuratowski subgraph isolation is requested for a dense graph
219	(a graph with <i>n = o(m)</i>) - the running time will be <i>O(n+m)</i>
220	<a href = "#2">[2]</a>.
221
222	<H3>Examples</H3>
223
224	<P>
225	<ul>
226	<li><a href="../example/simple_planarity_test.cpp">A simple planarity test</a>
227	<li><a href="../example/kuratowski_subgraph.cpp">Isolating a Kuratowski
228	Subgraph</a>
229	<li><a href="../example/straight_line_drawing.cpp">Using a planar embedding to
230	create a straight line drawing</a>
231	</ul>
232
233	<h3>See Also</h3>
234
235	<a href="./planar_graphs.html">Planar Graphs in the Boost Graph Library</a>
236
237
238	<h3>Notes</h3>
239
240	<p><a name="1">[1] A planar embedding is also called a <i>combinatorial
241	embedding</i>.
242
243	<p><a name="2">[2] The algorithm can still be made to run in time <i>O(n)</i>
244	for this case, if needed. <a href="planar_graphs.html#EulersFormula">Euler's
245	formula</a> implies that a planar graph with <i>n</i> vertices can have no more
246	than <i>3n - 6</i> edges, which means that any non-planar graph on <i>n</i>
247	vertices has a subgraph of only <i>3n - 5</i> edges that contains a Kuratowski
248	subgraph. So, if you need to find a Kuratowski subgraph of a graph with more
249	than <i>3n - 5</i> edges in time <i>O(n)</i>, you can create a subgraph of the
250	original graph consisting of any arbitrary <i>3n - 5</i> edges and pass that
251	graph to <tt>boyer_myrvold_planarity_test</tt>.
252
253
254	<br>
255	<HR>
256	Copyright © 2007 Aaron Windsor (<a href="mailto:aaron.windsor@gmail.com">
257	aaron.windsor@gmail.com</a>)
258	</BODY>
259	</HTML>