Do you know a faster algorithm to color planar graphs?

Question

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/

Answer 1

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.

Answer 2

I was asked to join my two answers, although they have not much in common.

NEW ANSWER:

I looked into your 4ct.py code and found this:

... Create a random planar graph from the dual of a RandomTriangulation (Sage function) of %s vertices. It may take very long time depending on the number of vertices ...

In 1994 I created code that can create maximal planar embedding very fast. Today I created github repo from that code, it can create random maximal planar graph embedding on 1,000,000 vertices in 3 seconds on an Intel i7 CPU (single core) Ubuntu: randomgraph github repo

Next I found in your code that you color the (triangular) faces of a random maximal planar graph (or the vertices of its dual cubic graph). Here I have to say that your code solves the wrong problem. While planar graphs in general are 4-colorable, planar cubic graphs different to K₄ (complete graph on 4 vertices) are 3-colorable, and therefore the faces of a maximal planar graph can be colored with at most 3 colors! Brooks theorem

There is a (fast) linear time algorithm that can 3-color any cubic planar graph different to K₄: Δ-List vertex coloring in linear time

OLD ANSWER:

There is a linear time algorithm to 5-color a planar graph: see Wikipedia.

I have implemented my under active development planar_graph_playground. The undirected graph library is implemented in NodeJS, Python and C++. Algorithms mostly look the same (design goal), using anonymous functions in NodeJS, lambdas in Python and C++ lambdas which are a bit different.

I have implemented a simple 6-coloring algorithm, and there are big sample graphs in the repo. On Intel i7 python you get 6-coloring in 1.5s/17.5s of the faces of a maximal planar graph (the vertices of its dual graph) for 10,000 / 100,000 vertices graphs:

$ time ( ./rpy python_6coloring.py ../graphs/10000.a > out )

real    0m1.449s
user    0m1.517s
sys     0m0.190s
$ time ( ./rpy python_6coloring.py ../graphs/100000.a > out )

real    0m17.446s
user    0m17.187s
sys     0m0.586s
$

Same algorithm in C++ 6-colors 500,000 / 1,000,000 vertices maximal planar graph faces in 9.7s/20.7s:

$ time (./c++_6coloring ../graphs/500000.a > out )

real    0m9.770s
user    0m9.606s
sys 0m0.163s
$ time (./c++_6coloring ../graphs/1000000.a > out )

real    0m20.772s
user    0m20.410s
sys 0m0.365s
$

PostScript 6-coloring of planar C60 fullerene

Answer 3

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)