From: Aaron Windsor (aaron.windsor_at_[hidden])
Date: 2007-04-01 12:04:26
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.
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
- 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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk