11
$\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
  • 2
    $\begingroup$ You don't explicitly say so, but I assume by "coloring" you mean "4-coloring". $\endgroup$ Oct 18, 2016 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$ Oct 19, 2016 at 0:51

3 Answers 3

6
$\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$
3
1
$\begingroup$

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

$\endgroup$
3
  • 3
    $\begingroup$ This is an algorithm for the 5-colour problem, while the OP is interested in the 4-colour problem. This post answers a question that has not been asked, and does not answer what has been asked. $\endgroup$
    – Alex M.
    Jun 21 at 17:11
  • 2
    $\begingroup$ This does not provide an answer to the question. Once you have sufficient reputation you will be able to comment on any post; instead, provide answers that don't require clarification from the asker. - From Review $\endgroup$
    – Alex M.
    Jun 21 at 17:11
  • 1
    $\begingroup$ OP poster searched for fast 4-coloring algorithm for planar graphs, which is unlikely to exist. So link to linear time 5-coloring algorithm is next best to what OP asked for. 6-coloring is only mentioned because there is a fast Python implementation for 6-coloring, which might satisfy OP as well. $\endgroup$
    – HermannSW
    Jun 21 at 17:26
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$
14
  • $\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$ Jan 3, 2019 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$ Jan 3, 2019 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, 2019 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$ Jan 6, 2019 at 8:39
  • 1
    $\begingroup$ @prusswan I'm using the same method as you mentioned here to color my graph with about 3k nodes and 10k edges. It works well and efficiently when the coloring number is equal or greater than 5, but raises the following error when changing the number to 4, ModuleNotFoundError: No module named 'sage_numerical_backends_gurobi'. I'm using Win10 with SageMath 9.3 installed. Do you know how to solve the problem? Or is there any fast implementation of the four color theorem? $\endgroup$
    – ReZhacai
    Apr 7 at 12:31

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.