...one of the most highly
regarded and expertly designed C++ library projects in the
world.

— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards

A graph is *planar* 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
*plane drawing*. Each
plane drawing belongs to an equivalence class called a *planar embedding*
[1] 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.

The function `boyer_myrvold_planarity_test` implements the planarity
testing/embedding algorithm of Boyer and Myrvold
[70].
`boyer_myrvold_planarity_test` returns `true` if the input graph
is planar and `false` 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 Kuratowski
subgraph can be found if the graph is not planar.
`boyer_myrvold_planarity_test` uses named parameter arguments (courtesy
of the Boost.Parameter
library) to specify what the function actually does. Some examples are:

- Testing whether or not a graph is planar:
bool is_planar = boyer_myrvold_planarity_test(g);

- Computing a planar embedding for a graph if it is planar, otherwise finding
a set of edges that forms an obstructing Kuratowski subgraph:
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 }

The parameters passed to `boyer_myrvold_planarity_test` 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.

`boyer_myrvold_planarity_test` 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 *n* vertices that lacks one of these
properties can be augmented with additional edges so that it satisfies that
property in *O(n)* time - the functions
`make_connected`,
`make_biconnected_planar`,
and `make_maximal_planar`
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
*before* passing it into `boyer_myrvold_planarity_test` so that the
computed planar embedding includes these additional edges. This may require
more than one call to `boyer_myrvold_planarity_test` depending on the
structure of the graph you begin with, since both
`make_biconnected_planar` and `make_maximal_planar` require a
planar embedding of the existing graph as an input parameter.

The named parameters accepted by `boyer_myrvold_planarity_test` are:

: The input graph - this is the only required parameter.`graph`: A mapping from vertices of the input graph to indexes in the range`vertex_index_map``[0..num_vertices(g))`. 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`get(vertex_index, g)`.: A mapping from the edges of the input graph to indexes in the range`edge_index_map``[0..num_edges(g))`. This parameter is only needed if the`kuratowski_subgraph`argument is provided. If the`kuratowski_subgraph`argument is provided and this parameter is not provided, the EdgeIndexMap is assumed to be available as an interior property accessible by calling`get(edge_index, g)`.: If the graph is planar, this will be populated with a mapping from vertices to the clockwise order of neighbors in the planar embedding.`embedding`: If the graph is not planar, a minimal set of edges that form the obstructing Kuratowski subgraph will be written to this iterator.`kuratowski_subgraph`

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 `
chrobak_payne_straight_line_drawing`) and using the function
`is_straight_line_drawing`
to verify that the resulting graph is planar.

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 `is_kuratowski_subgraph
` to verify that they can be contracted into a *K _{5}* or

`boost/graph/boyer_myrvold_planar_test.hpp`

Any undirected graph. The graph type must be a model of VertexAndEdgeListGraph and IncidenceGraph.OUT

Must model the PlanarEmbedding concept.IN

An OutputIterator which accepts values of the typeINgraph_traits<Graph>::edge_descriptor

A Readable Property Map that maps vertices fromINgto distinct integers in the range[0, num_vertices(g) )

Default:get(vertex_index,g)

A Readable Property Map that maps edges fromgto distinct integers in the range[0, num_edges(g) )

Default:get(edge_index,g), but this parameter is only used if thekuratowski_subgraph_iteratoris provided.

- A simple planarity test
- Isolating a Kuratowski Subgraph
- Using a planar embedding to create a straight line drawing

[1] A planar embedding is also called a *combinatorial
embedding*.

[2] The algorithm can still be made to run in time *O(n)*
for this case, if needed. Euler's
formula implies that a planar graph with *n* vertices can have no more
than *3n - 6* edges, which means that any non-planar graph on *n*
vertices has a subgraph of only *3n - 5* edges that contains a Kuratowski
subgraph. So, if you need to find a Kuratowski subgraph of a graph with more
than *3n - 5* edges in time *O(n)*, you can create a subgraph of the
original graph consisting of any arbitrary *3n - 5* edges and pass that
graph to `boyer_myrvold_planarity_test`.

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