Boost Graph Library: Boyer-Myrvold Planarity Testing/Embedding

# Boyer-Myrvold Planarity Testing/Embedding

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.

##### A planar graph (top left), along with a planar embedding of that graph (bottom left) can be used to create a plane drawing (right) by embedding edges around each vertex in the order in which they appear in the planar embedding.

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:

- `graph` : The input graph - this is the only required parameter.
- `vertex_index_map` : A mapping from vertices of the input graph to indexes in the range `[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)`.
- `edge_index_map`: A mapping from the edges of the input graph to indexes in the range `[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)`.
- `embedding` : If the graph is planar, this will be populated with a mapping from vertices to the clockwise order of neighbors in the planar embedding.
- `kuratowski_subgraph` : If the graph is not planar, a minimal set of edges that form the obstructing Kuratowski subgraph will be written to this iterator.

These named parameters all belong to the namespace `boyer_myrvold_params`. See below for more information on the concepts required for these arguments.

### Verifying the output

Whether or not the input graph is planar, `boyer_myrvold_planarity_test` can produce a certificate that can be automatically checked to verify that the function is working properly.

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 K5 or K3,3. `boyer_myrvold_planarity_test` chooses the set of edges forming the Kuratowski subgraph in such a way that the contraction to a K5 or K3,3 can be done by a simple deterministic process which is described in the documentation to `is_kuratowski_subgraph`.

### Where Defined

`boost/graph/boyer_myrvold_planar_test.hpp`

### Parameters

IN: `Graph& g`

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

OUT `PlanarEmbedding embedding`

> Must model the PlanarEmbedding concept.

IN `OutputIterator kuratowski_subgraph`

> An OutputIterator which accepts values of the 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)`

IN `EdgeIndexMap em`

> A Readable Property Map that maps edges from `g` to distinct integers in the range `[0, num_edges(g) )`
> Default: `get(edge_index,g)`, but this parameter is only used if the `kuratowski_subgraph_iterator` is provided.

### Complexity

Assuming that both the vertex index and edge index supplied take time O(1) to return an index and there are O(n) total self-loops and parallel edges in the graph, most combinations of arguments given to `boyer_myrvold_planarity_test` result in an algorithm that runs in time O(n) for a graph with n vertices and m edges. The only exception is when Kuratowski subgraph isolation is requested for a dense graph (a graph with n = o(m)) - the running time will be O(n+m) [2].

### Examples

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

### See Also

Planar Graphs in the Boost Graph Library

### Notes

[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)