[Graph theory] Coloring a planar graph

Discussion in 'Math Research' started by sylsau14, Dec 19, 2005.

  1. sylsau14

    sylsau14 Guest

    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.
     
    sylsau14, Dec 19, 2005
    #1
    1. Advertisements

  2. 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
     
    Larry Hammick, Feb 8, 2006
    #2
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.