Crossposted from: <https://math.stackexchange.com/questions/1964486/which-is-the-most-time-efficient-algorithm-for-having-a-tait-coloring-edge>


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)

```


Which is the most time efficient algorithm for having a Tait Coloring (edge-3-coloring) of planar cubic graphs?
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.


