6
$\begingroup$

while studying the four color theorem, I implemented an algorithm (in Python and Sage) that can color planar graphs much faster than the implementations I found around on internet.

The program can be downloaded here: https://sourceforge.net/p/maps-coloring/code/ci/master/tree/ct/ct-sage/4ct.py

It requires sage to be executed:

  • sage 4ct.py --help

I haven't tried many tools or library, like Mathematica, networkx or others, but the difference with the Sage implementation edge_coloring() is promising.

I have two questions:

  • Is this approach to coloring planar graphs already known/used (see bolow)?
  • Can you help me identifying faster known implementation for edge coloring?

The algorithm considers Tait edge coloring and the equivalency of the 3-edge-coloring (known as Tait coloring) and the 4-face-coloring (the original four color theorem for maps).

The algorithm goes like this:

  • It uses a modified Kempe reduction method: it does not shrink a face (faces <= F5) down to a point, but removes a single edge from it (from faces <= F5)
  • It uses a modified Kempe chain edge color switching: when restoring edges from the reduced graph, it will swap half of the colored Kempe loop

Note that while rebuilding a map, all Kempe chains are actually Kempe loops!!!

These are the stats:

  • 100 – 196 vertices, 294 edges = 0 seconds
  • 200 – 396 vertices, 594 edges = 1 seconds
  • 300 – 596 vertices, 894 edges = 4 seconds
  • 400 – 796 vertices, 1194 edges = 6 seconds
  • 500 – 996 vertices, 1494 edges = 8 seconds
  • 600 – 1196 vertices, 1794 edges = 10 seconds
  • 700 – 1396 vertices, 2094 edges = 16 seconds
  • 800 – 1596 vertices, 2394 edges = 18 seconds
  • 900 – 1796 vertices, 2694 edges = 22 seconds
  • 1000 – 1996 vertices, 2994 edges = 26 seconds

Almost linear … what do you think?

The first column is the original number of vertices for the planar triangulation from which the dual graph (a cubic planar graph) is computed. The seconds reported above do not consider the time to load or create the imput graph and to compute the planar embedding. You can also upload an already planar embedded graph using the -p option.

The same problem of coloring the egdes using the Sage function edge_coloring() requires very long time. I run 15 tests, and to color random graphs with 196 vertices and 294 edges, took: 7, 73, 54, 65, 216, 142, 15, 14, 21, 73, 24, 15, 32, 72, 232 seconds, for the same case where my algorithm takes less than 1 second: 100 – 196 vertices, 294 edges.

https://4coloring.wordpress.com/2016/10/16/four-color-theorem-a-fast-algorithm/

$\endgroup$
  • 2
    $\begingroup$ You don't explicitly say so, but I assume by "coloring" you mean "4-coloring". $\endgroup$ – Gerry Myerson Oct 18 '16 at 22:26
  • $\begingroup$ Edge coloring using 3 colors, known as Tait coloring. It is equivalent to the four cilor theorem for the faces $\endgroup$ – Mario Stefanutti Oct 19 '16 at 0:51
4
$\begingroup$

It sounds to me that you're not claiming that your algorithm is guaranteed to find a 4-coloring of a planar graph, just that it usually does so very quickly.

A standard reference for heuristic algorithms for coloring planar graphs is "Heuristics for Rapidly Four-Coloring Large Planar Graphs," by Craig A. Morgenstern and Henry D. Shapiro, Algorithmica 6 (1991), 869–891. They do use a modification of Kempe chain ideas, but I don't know if it's the same as yours.

You didn't specify which "implementations you found around the internet," so maybe you already know about this, but ColPack is one such package that you might try, if you haven't already. There is a paper on ColPack that describes it in detail.

$\endgroup$
0
$\begingroup$

I tried your program, which unfortunately does not work because it only works with planar and cubic graphs. This means it would not work with most graphs derived from real-world maps that are certainly planar but not likely to have the same degree for all the vertices.

That said, through your project (which uses Sage), I found out that Sage + Gurobi can handle a 10k nodes planar graph in a matter of minutes (using their proprietary linear programming solver).

The code is very simple (just construct the graph and call the LP solver):

import networkx as nx
ng = nx.readwrite.gpickle.read_gpickle('some_graph.pickle')
G = Graph(ng) # my graph is stored in networkx format

from sage.graphs.graph_coloring import vertex_coloring
coloring = vertex_coloring(G, 4, solver="Gurobi", verbose=10)
$\endgroup$
  • $\begingroup$ Considering only cubic graphs is the standard approach four maps. From Wikipedia: Kempe's argument goes as follows. First, if planar regions separated by the graph are not triangulated, i.e. do not have exactly three edges in their boundaries, we can add edges without introducing new vertices in order to make every region triangular, including the unbounded outer region. If this triangulated graph is colorable using four colors or fewer, so is the original graph since the same coloring is valid if edges are removed. So it suffices to prove the four color theorem for triangulated graphs to prov $\endgroup$ – Mario Stefanutti Jan 3 at 0:12
  • $\begingroup$ About Sage I am planning to remove this dependemcy and use networkx instead. Can you also share the link to the Sage+Gurobi algorithm, I would like to try it. Thanks in advance. $\endgroup$ – Mario Stefanutti Jan 3 at 0:18
  • $\begingroup$ @MarioStefanutti I see, maybe if there is a way for me to apply this result (e.g. convert planar graph to cubic graph -> 4-color cubic graph -> 4-color original planar graph) then it can be more useful. My interest is to use this to color actual maps $\endgroup$ – prusswan Jan 3 at 4:09
  • $\begingroup$ To tramsform the graph to cubic, consider a vertex that has more than 3 edge and make a small circle that has the vertex as the center and remove all edges inside the circle. If you do that four all vertex that have more than 3 edges. At the end you will have a cubic graph. If you can color this, just shrink down to a point all circles that were added $\endgroup$ – Mario Stefanutti Jan 6 at 8:39
  • $\begingroup$ about the real map you want to color do you have a graph representation of it or just the printed map? $\endgroup$ – Mario Stefanutti Jan 6 at 8:43

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.