Crossposted from: http://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)