Boost logo

Boost Users :

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 to

(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
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


Boost-users list run by williamkempf at, kalb at, bjorn.karlsson at, gregod at, wekempf at