Do you know a faster algorithm to color planar graphs?

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.

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/

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

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.

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