
Boost Users : 
Subject: [Boostusers] Some results for planar graph coloring algorithm
From: Mike Douglass (douglassm13_at_[hidden])
Date: 20100704 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
Boostusers list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net