417.sagews

Here are some functions which compute the dual of a planar graph. Currently, I don't think there is any error checking, and I don't remember if I decided that this implementation was correct or not. However, the dual computed in the example below is correct. I think that it works.

def faces(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

def graph_dual(g):
    f = [tuple(face) for face in faces(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

h=graphs.PathGraph(2)
g=h.disjoint_union(h).disjoint_union(h)
g=g.complement()
g.relabel()
show(g)

g.is_planar(set_embedding=True, set_pos=True)
show(g)

# The vertices forming the faces of the graph
faces(g)

[[0, 5, 2], [0, 4, 3], [0, 2, 4], [0, 3, 5], [1, 4, 2], [1, 5, 3], [1, 3, 4], [1, 2, 5]]

dual_g=graph_dual(g)

# Each vertex is labeled with the edges of the face that it represents.
show(dual_g)

# We can relabel the vertices to get a "nice" graph, but then we lose the information about which face corresponds to which vertex.
dual_g.relabel()
show(dual_g)