Boost C++ Libraries

...one of the most highly regarded and expertly designed C++ library projects in the world. Herb Sutter and Andrei Alexandrescu, C++ Coding Standards

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 K5 or K3,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 K5 or K3,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 K3,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 K5.

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 K5, 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 K5 or a K3,3 and to determinstically contract the vertices of degree 4 once the K5 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)