# Which is the most time efficient algorithm for having a Tait Coloring (edge-3-coloring) of planar cubic graphs?

I wasn't able to find an efficient algorithm nor an implementation in Sage to efficiently color the edges of a cubic planar graph.

The sage function that I found is: sage.graphs.graph_coloring.edge_coloring

That seems generic for graphs (non only planar graphs). 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

If I increase the number of vertices and edges, the edge_coloring funtion takes very long time.

Can you address me to more efficient edge coloring algorithms (only three colors to use) in Sage or other frameworks (or a reference to papers), for planar embedded graphs (cubic graphs)?

from sage.graphs.graph_coloring import edge_coloring
from datetime import datetime

###########################################################################
# Return a face as a list of ordered vertices. Used to create random graphs
# Taken on the internet (http://trac.sagemath.org/ticket/6236)
###########################################################################
def faces_by_vertices(g):
d = {}
for key, val in g.get_embedding().iteritems():
d[key] = dict(zip(val, val[1:] + [val[0]]))
list_faces = []
for start in d:
while d[start]:
face = []
prev = start
_, curr = d[start].popitem()
face.append(start)
while curr != start:
face.append(curr)
prev, curr = (curr, d[curr].pop(prev))
list_faces.append(face)

return list_faces

#################################################################################################
# Return the dual of a graph. Used to create random graphs
# Taken on the internet: to make a dual of a triangulation (http://trac.sagemath.org/ticket/6236)
#################################################################################################
def graph_dual(g):
f = [tuple(face) for face in faces_by_vertices(g)]
f_edges = [tuple(zip(i, i[1:] + (i[0],))) for i in f]
dual = Graph([f_edges, lambda f1, f2: set(f1).intersection([(e[1], e[0]) for e in f2])])

return dual

for i in range(15):
tmp_g = graphs.RandomTriangulation(100)  # Random triangulation on the surface of a sphere
void = tmp_g.is_planar(set_embedding = True, set_pos = True)  # Cannot calculate the dual if the graph has not been embedded
the_graph = graph_dual(tmp_g)  # The dual of a triangulation is a 3-regular planar graph
the_graph.allow_loops(False)
the_graph.allow_multiple_edges(False)
void = the_graph.relabel()  # The dual of a triangulation will have vertices represented by lists - triangles (v1, v2, v3) instead of a single value

t1 = datetime.now()
void = edge_coloring(the_graph)
t2 = datetime.now()
delta = t2 - t1
print ("Execution number: ", i, ", time: ", delta.seconds)


There is a quadratic-time algorithm for 3-edge-colouring a planar cubic graph, as described in the accepted answer to:

https://cstheory.stackexchange.com/questions/2578/complexity-of-edge-coloring-in-planar-graphs

Specifically, do the following:

• Find an embedding of the graph in the plane (which takes linear time);
• Create the planar dual graph (straightforward);
• Find a 4-colouring of the dual graph (quadratic time);
• Compute the associated 3-edge-colouring of the original graph (again, straightforward).

I don't know whether this has been implemented in software.

• One step of this is locating one of the 600+ unavoidable configurations in the planar graph, which sounds like something difficult to implement. – Gordon Royle Oct 17 '16 at 9:23