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)
