[boost] [BGL] Tools for planar graph testing/embedding/drawing in the vault

From: Aaron Windsor (aaron.windsor_at_[hidden])
Date: 2007-04-01 12:04:26

Hi all,

I've implemented a small suite of tools for dealing with planar graphs and
would like to add it to the BGL. The core of this suite is built around the
recent Boyer-Myrvold algorithm for planarity testing/embedding.
(see http://www.emis.de/journals/JGAA/accepted/2004/BoyerMyrvold2004.8.3.pdf)

A graph is planar if it can be drawn in two-dimensional space with no edge
crossings. A graph is non-planar exactly when it contains a subgraph that is
an expansion of one of two special subgraphs, called "Kuratowski subgraphs."
This face makes it possible not only to detect that a graph is non-planar,
but to prove it's non-planar by isolating one of these subgraphs. In addition
to the obvious applications to graph-drawing, planar graphs are often simpler
to deal with in optimization problems, and many problems that are NP-complete
(most likely requiring exponential time to solve) have efficient algorithms
or better approximation guarantees for the special case of planar graphs.

The functions I've implemented allow one to:
- Test a graph for planarity.
- Embed a planar graph in the plane.
- Find and verify a minimal Kuratowski subgraph in a non-planar graph.
- Create a straight-line drawing of a planar graph (a mapping of vertices to
  points in the plane such that all edges can be drawn with straight line
  segments).
- Traverse the faces of a planar graph using generic visitor event points
  in the spirit of the BGL depth-first and breadth-first search algorithms.
  With appropriate visitors, this traversal can be used to count the faces
  of a planar graph, triangulate a planar graph, or find a dual of a planar
  graph, among other things.

With a few caveats about the efficiency of vertex index maps, etc. all of the
functions above run in linear time with respect to the number of vertices in
the graph, which is optimal.

I've put two sets of files in the vault under Home/Algorithms/graph: the
first is called planar_graphs.zip (also planar_graphs.tar.gz) and contains
the .hpp files, the documentation, and the examples. The second is called
planar_graph_testing.zip (also planar_graph_testing.tar.gz) and contains
over 1000 test graphs and a small program that can be compiled to give an
example of how these planar graph tools can be used. I'd appreciate any
comments!

Regards,
Aaron