[Graph theory] Coloring a planar graph

Hi,

I'm going to do a program who let to detect if a graph is planar or no.
The program runs very well.
The goal of this first stage was to have planar graph to color.
Indeed, this graphs have got particulars properties which let to color
these with better algorithm than classical graph.

So, I must find an algorithm using this properties.

The problem is that I don't arrive to know how to begin in my
algorithm. What properties are the most interesting for the
coloration ?
(I know a planar graph is 5-coloriable, but I don't see how use this in
an algorithm in fact).


If someone had an idea or a link on the web, I would be interested.

Thanks to you.

Sylvain.

 

You might look at "Schnyder's algorithm". It is an algorithm for embedding a
maximally planar graph in the plane, but it has additional interest. The
edges of the graph get partitioned into three forest graphs A,B,C, and those
can each be oriented such that A \cup B (or any other 2 of the 3) become a
poset for which a constructive 3-coloration is immediate. Therefore the
whole graph is trivialy 6-colourable; but for fewer colors, it might still
be useful. At least, a forest order is well-suited to any reentrant
algorithm which uses a sort of "stack" structure.
If you use Schnyder, I would advise adjoining 3 new vertices in the
"unbounded face" of the graph, and joining them to some of the original
vertices such that the posets become trees, not just forests. It simplifies
things.
Larry Hammick
Vancouver