1 <html><head><!-- Copyright 2007 Aaron Windsor
3 Distributed under the Boost Software License, Version 1.0.
4 (See accompanying file LICENSE_1_0.txt or copy at
5 http://www.boost.org/LICENSE_1_0.txt)
8 <title>Boost Graph Library: is_kuratowski_subgraph
</title>
15 <img src=
"../../../boost.png" alt=
"C++ Boost" height=
"86" width=
"277">
19 <h1><tt>is_kuratowski_subgraph
</tt></h1>
21 <pre>template
<typename Graph, typename ForwardIterator, typename VertexIndexMap
>
22 bool is_kuratowski_subgraph(const Graph
& g, ForwardIterator begin, ForwardIterator end, VertexIndexMap vm)
27 <tt>is_kuratowski_subgraph(g, begin, end)
</tt> returns
<tt>true
</tt> exactly
28 when the sequence of edges defined by the range
<tt>[begin, end)
</tt> forms a
29 <a href=
"./planar_graphs.html#kuratowskisubgraphs"> Kuratowski subgraph
</a> in
30 the graph
<tt>g
</tt>. If you need to verify that an arbitrary graph has a
31 <i>K
<sub>5</sub></i> or
<i>K
<sub>3,
3</sub></i> minor, you should use the
32 function
<tt><a href=
"boyer_myrvold.html">boyer_myrvold_planarity_test
</a></tt>
33 to isolate such a minor instead of this function.
<tt>is_kuratowski_subgraph
34 </tt> exists to aid in testing and verification of the function
35 <tt>boyer_myrvold_planarity_test
</tt>, and for that reason, it expects its
36 input to be a restricted set of edges forming a Kuratowski subgraph, as
37 described in detail below.
39 <tt>is_kuratowski_subgraph
</tt> creates a temporary graph out of the sequence
40 of edges given and repeatedly contracts edges until it ends up with a graph
41 with either all edges of degree
3 or all edges of degree
4. The final
42 contracted graph is then checked against
<i>K
<sub>5</sub></i> or
43 <i>K
<sub>3,
3</sub></i> using the Boost Graph Library's
44 <a href=
"isomorphism.html">isomorphism
</a>
45 function. The contraction process starts by choosing edges adjacent to a vertex
46 of degree
1 and contracting those. When none are left, it moves on to edges
47 adjacent to a vertex of degree
2. If only degree
3 vertices are left after this
48 stage, the graph is checked against
<i>K
<sub>3,
3</sub></i>. Otherwise, if
49 there's at least one degree
4 vertex, edges adjacent to degree
3 vertices are
50 contracted as neeeded and the final graph is compared to
<i>K
<sub>5</sub></i>.
52 In order for this process to be deterministic, we make the following two
53 restrictions on the input graph given to
<tt>is_kuratowski_subgraph
</tt>:
55 <li>No edge contraction needed to produce a kuratowski subgraph results in
56 multiple edges between the same pair of vertices (No edge
<i>{a,b}
</i> will be
57 contracted at any point in the contraction process if
<i>a
</i> and
<i>b
</i>
58 share a common neighbor.)
59 </li><li>If the graph contracts to a
<i>K
<sub>5</sub></i>, once the graph has
60 been contracted to only vertices of degree at least
3, no cycles exist that
61 contain solely degree
3 vertices.
63 The second restriction is needed both to discriminate between targeting a
64 <i>K
<sub>5</sub></i> or a
<i>K
<sub>3,
3</sub></i> and to determinstically
65 contract the vertices of degree
4 once the
<i>K
<sub>5</sub></i> has been
66 targeted. The Kuratowski subgraph output by the function
<tt>
67 <a href=
"boyer_myrvold.html">boyer_myrvold_planarity_test
</a></tt> is
68 guaranteed to meet both of the above requirements.
73 On a graph with
<i>n
</i> vertices, this function runs in time
<i>O(n)
</i>.
75 <h3>Where Defined
</h3>
78 <a href=
"../../../boost/graph/is_kuratowski_subgraph.hpp">
79 <tt>boost/graph/is_kuratowski_subgraph.hpp
</tt>
82 </p><h3>Parameters
</h3>
84 IN:
<tt>Graph
& g
</tt>
87 An undirected graph with no self-loops or parallel edges. The graph type must
88 be a model of
<a href=
"VertexListGraph.html">Vertex List Graph
</a>.
91 IN:
<tt>ForwardIterator
</tt>
94 A ForwardIterator with value_type
95 <tt>graph_traits
<Graph
>::edge_descriptor
</tt>.
98 IN:
<tt>VertexIndexMap vm
</tt>
101 A
<a href=
"../../property_map/doc/ReadablePropertyMap.html">Readable Property Map
102 </a> that maps vertices from
<tt>g
</tt> to distinct integers in the range
103 <tt>[
0, num_vertices(g) )
</tt><br>
104 <b>Default
</b>:
<tt>get(vertex_index,g)
</tt><br>
111 <a href=
"../example/kuratowski_subgraph.cpp">
112 <tt>examples/kuratowski_subgraph.cpp
</tt>
115 </p><h3>See Also
</h3>
118 <a href=
"planar_graphs.html">Planar Graphs in the Boost Graph Library
</a>
123 Copyright ©
2007 Aaron Windsor (
<a href=
"mailto:aaron.windsor@gmail.com">
124 aaron.windsor@gmail.com
</a>)