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
$
