`is_kuratowski_subgraph`

template <typename Graph, typename ForwardIterator, typename VertexIndexMap>
bool is_kuratowski_subgraph(const Graph& g, ForwardIterator begin, ForwardIterator end, VertexIndexMap vm)

`is_kuratowski_subgraph(g, begin, end)` returns `true` exactly
when the sequence of edges defined by the range `[begin, end)` forms a
Kuratowski subgraph in
the graph `g`. If you need to verify that an arbitrary graph has a
*K*_{5} or *K*_{3,3} minor, you should use the
function `boyer_myrvold_planarity_test`
to isolate such a minor instead of this function. `is_kuratowski_subgraph
` exists to aid in testing and verification of the function
`boyer_myrvold_planarity_test`, and for that reason, it expects its
input to be a restricted set of edges forming a Kuratowski subgraph, as
described in detail below.

`is_kuratowski_subgraph` creates a temporary graph out of the sequence
of edges given and repeatedly contracts edges until it ends up with a graph
with either all edges of degree 3 or all edges of degree 4. The final
contracted graph is then checked against *K*_{5} or
*K*_{3,3} using the Boost Graph Library's
isomorphism
function. The contraction process starts by choosing edges adjacent to a vertex
of degree 1 and contracting those. When none are left, it moves on to edges
adjacent to a vertex of degree 2. If only degree 3 vertices are left after this
stage, the graph is checked against *K*_{3,3}. Otherwise, if
there's at least one degree 4 vertex, edges adjacent to degree 3 vertices are
contracted as neeeded and the final graph is compared to *K*_{5}.

In order for this process to be deterministic, we make the following two
restrictions on the input graph given to `is_kuratowski_subgraph`:

- No edge contraction needed to produce a kuratowski subgraph results in
multiple edges between the same pair of vertices (No edge
*{a,b}* will be
contracted at any point in the contraction process if *a* and *b*
share a common neighbor.)
- If the graph contracts to a
*K*_{5}, once the graph has
been contracted to only vertices of degree at least 3, no cycles exist that
contain solely degree 3 vertices.

The second restriction is needed both to discriminate between targeting a
*K*_{5} or a *K*_{3,3} and to determinstically
contract the vertices of degree 4 once the *K*_{5} has been
targeted. The Kuratowski subgraph output by the function `
boyer_myrvold_planarity_test` is
guaranteed to meet both of the above requirements.
### Complexity

On a graph with *n* vertices, this function runs in time *O(n)*.
### Where Defined

`boost/graph/is_kuratowski_subgraph.hpp`

### Parameters

IN: `Graph& g`
An undirected graph with no self-loops or parallel edges. The graph type must
be a model of Vertex List Graph.

IN: `ForwardIterator`
A ForwardIterator with value_type
`graph_traits<Graph>::edge_descriptor`.

IN: `VertexIndexMap vm`
A Readable Property Map
that maps vertices from `g` to distinct integers in the range
`[0, num_vertices(g) )`

**Default**: `get(vertex_index,g)`

### Example

`examples/kuratowski_subgraph.cpp`

### See Also

Planar Graphs in the Boost Graph Library

Copyright © 2007 Aaron Windsor (
aaron.windsor@gmail.com)