
Boost : 
From: Aaron Windsor (aaron.windsor_at_[hidden])
Date: 20070401 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 BoyerMyrvold 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 twodimensional space with no edge
crossings. A graph is nonplanar 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 nonplanar,
but to prove it's nonplanar by isolating one of these subgraphs. In addition
to the obvious applications to graphdrawing, planar graphs are often simpler
to deal with in optimization problems, and many problems that are NPcomplete
(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 nonplanar graph.
 Create a straightline 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 depthfirst and breadthfirst 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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk