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

From: Jens Müller (jens.mueller_at_[hidden])
Date: 2007-07-02 19:45:33

Aaron Windsor wrote:
> 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!

Aaron Windsor wrote:

1. It would be nice if bidirectional graphs could be supported as well.

2. I have an (directed) graph which should be planar:

      http://i11www.iti.uni-karlsruhe.de/~jmueller/100x250.graphml

   I read it into a LEDA graph using the GraphML reader from graph-tool.
   LEDA confirms that the graph is indeed planar.

   To test it with your implementation, I changed it to undirected

   edges:

http://i11www.iti.uni-karlsruhe.de/~jmueller/100x250-undirected.graphml

   I read it into a boost::adjacency_list with undirectedS
directionality (instead of bidirectionalS which I would be using
normally), and boyer_myrvold_planarity_test returns false ...

Maybe you can take a look at the graph?

3. What is your implementation doing when the graph is not undirected or
when there are self-loops?

Best wishes,

Jens