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