[Boost-users] Some results for planar graph coloring algorithm

Subject: [Boost-users] Some results for planar graph coloring algorithm
From: Mike Douglass (douglassm13_at_[hidden])
Date: 2010-07-04 19:11:50

I have uploaded Planar6_July3.tz to

http://groups.google.com/group/graph_coloring_program

(README_July3) .

It contains 100 maximal planar graphs of 50 vertices each.
The graphs were generated using LEDA's function
maximal_planar_graph(graph, number_of_vertices).

I applied my graph coloring program "pl" in batch mode (using a perl script) to a
directory containing the 100 graphs and it succeeded in finding a proper 4 coloring for
EVERY SINGLE GRAPH.
Average solution time per graph - about 1 second, of which a large part was 
probably disk read/writes.

Does anyone have a favorite planar graph of <= 50 vertices that I can try my algorithm on?
50 vertices is not very large, but soon I hope to try graphs of 60, 70 or more vertices.

I ran fr_layout on the 100 graphs but the resulting layout was not very clear. I think what 
I really need is a layout on a sphere and a way to look at the sphere from any angle. Does
anyone know of such a thing. In the not too distant future I hope to be looking at graphs
of up to 100 vertices. Anything but a spherical layout i believe would be too messy.

You can find a clear graphical depiction of the algorithm at

http://groups.google.com/group/graph_coloring_B1