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₅ 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₅ 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₅.

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

1. 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.)
2. If the graph contracts to a K₅, once the graph has been contracted to only vertices of degree at least 3, no cycles exist that contain solely degree 3 vertices.

Complexity

Where Defined

boost/graph/is_kuratowski_subgraph.hpp

Parameters

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

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

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