How do I get the external face of a planar embedded graph?

asked 2016-05-11 03:44:18 -0600

stefanutti gravatar image

First of all I am new to Sage and Python.

I need to get the external face a planar embedding and I immagined that it is always the first element returned by the function faces().

But in this example it seems to change. See the first and the second run.

Is it something about the function faces() or an error in this program?

print ("--- Create a graph")
G = Graph(sparse=True)
G.add_edge(1,2,"1-2")
G.add_edge(2,3,"2-3")
G.add_edge(3,4,"3-4")
G.add_edge(4,5,"4-5")
G.add_edge(5,1,"5-1")
G.add_edge(1,6,"1-6")
G.add_edge(2,10,"2-10")
G.add_edge(3,12,"3-12")
G.add_edge(4,11,"4-11")
G.add_edge(5,7,"5-7")
G.add_edge(6,7,"6-7")
G.add_edge(6,8,"6-8")
G.add_edge(8,10,"8-10")
G.add_edge(10,12,"10-12")
G.add_edge(12,11,"12-11")
G.add_edge(7,9,"7-9")
G.add_edge(8,9,"8-9")
G.add_edge(9,11,"9-11")

print ("--- Embed on a plane")
void = G.layout(layout = "planar", save_pos = True)

G.plot()

# Kempe reduction: for each loop remove an edge from faces <= F5
#
while len(G.faces()) > 2:

    print ("Number of faces: ", len(G.faces()))

    # Remove the external face. Is it always faces[0]???
    #
    faces = G.faces()
    externalFace = faces[0]
    facesWithoutTheExternalFace = copy(faces)
    facesWithoutTheExternalFace.remove(externalFace)
    print ("faces: ", faces)
    print ("externalFace: ", externalFace)
    print ("facesWithoutTheExternalFace: ", facesWithoutTheExternalFace)

    # Find the fist face [0] with len <= 5. It always exists: unavoidable set
    #
    faceToReduce = [x for x in facesWithoutTheExternalFace if len(x) <= 5][0]
    print ("Face <= 5: ", faceToReduce)

    # Find the first edge of the faceToReduce that is not on an edge on the external face
    #
    edgeToRemove = [x for x in faceToReduce if not x in externalFace][0]
    print ("edgeToRemove: ", edgeToRemove)

    verticesToRemove = G.get_vertices(edgeToRemove)
    print ("verticesToRemove ", verticesToRemove)

    G.delete_edge(edgeToRemove)
    neighborsOfTheFirstVertex = G.neighbors(verticesToRemove.keys()[0])
    neighborsOfTheSecondVertex = G.neighbors(verticesToRemove.keys()[1])
    print ("neighborsOfTheFirstVertex = ", neighborsOfTheFirstVertex)
    print ("neighborsOfTheSecondVertex = ", neighborsOfTheSecondVertex)
    G.delete_vertices(verticesToRemove)
    G.add_edge(neighborsOfTheFirstVertex[0], neighborsOfTheFirstVertex[1])
    G.add_edge(neighborsOfTheSecondVertex[0], neighborsOfTheSecondVertex[1])
    G.plot()
edit retag flag offensive close merge delete

Comments

What precisely do you mean by "external face"? Given the embedding returned by the .is_planar() implicit in G.layout(), any of the faces given could be considered the external face - embedding on the plane and the sphere are interchangeable under stereographic projection. In any case, if you are referring to external with respect to the graphics object output by G.plot(), it seems the original external face is still the "external face" after your first reduction, but your algorithm chooses a new external face.

Perhaps clarification of "external face" would help get you an answer more like what you're looking for.

JEFLSU gravatar imageJEFLSU ( 2016-05-31 15:11:44 -0600 )edit

Yes, I needed to get the external face respect to the particular planar embedding computed by the G.layout(layout = "planar", save_pos = True)

After the "planar embedding", the position of the vertices should be set (wikipedia: in which points of Σ are associated to vertices) and the external face shoud be also set.

In other words, as far as I know, yes you can embed the graph in many ways depending which face of the graph you want it to be the external face, but for a particular planar embedding the external face is set.

Anyway, at the end I decided to remove edges even if they were on the externall face.

stefanutti gravatar imagestefanutti ( 2016-05-31 17:14:45 -0600 )edit