3
$\begingroup$

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)
$\endgroup$
1
+50
$\begingroup$

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.

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

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.