9
$\begingroup$

Hi, I was looking to traverse a planar graph and report all the faces in the graph (vertices in either clockwise or counterclockwise order). I have build a random planar graph generator that creates a connected graph with iterative edge addition and needed a solution to report all the faces that were created in the final graph. I was contemplating several strategies such as doing a sweep line algorithm and tracking the areas between lines or tracking the faces as I generate the graph however I have not been able to find much material regarding this matter and was wondering where I could find some assistance/ideas how to do this.

So far I found a Boost algorithm here http://www.boost.org/doc/libs/1_36_0/boost/graph/planar_face_traversal.hpp however I am having a lot of trouble decrypting the boost library to determine how it is done.

Any thoughts, ideas or existing algorithms would be welcome.

$\endgroup$
4
  • $\begingroup$ This is very unclear. In what format do you have the graph? What exactly are you trying to report? Just the number of faces? That's easy via a degree-count and Euler's formula. And I'm not sure what clockwise and counterclockwise mean. $\endgroup$ May 7, 2010 at 5:27
  • $\begingroup$ @Cam, my reading is that Icemanxp has a plane graph, by which I mean a planar graph together with an embedding of the graph into the plane, in which case it's clear what clockwise and counterclockwise mean. I take it Icemanxp wants not just the number of faces but a listing of the faces, each face being given by a list of its vertices, the list of vertices being in (clockwise or counterclockwise) order around the face. I regret that I have no suggestion as to how Icemanxp might accomplish this goal. $\endgroup$ May 7, 2010 at 6:31
  • 2
    $\begingroup$ Yes Garry has the right idea. My graph is sitting on a plane and all my vertices are represented by a 2d point. No two edges cross each other except where they are connected at a vertex. Essentialy if my graph was a road network of a city (edge is a road, vertex is an intersection) I would like a list of the contours of every block in the city, as being defined as a clockwise or counter-clockwise list of points/vertices. $\endgroup$
    – Icemanxp
    May 7, 2010 at 19:34
  • $\begingroup$ Err Gerry :/ sorry $\endgroup$
    – Icemanxp
    May 7, 2010 at 19:35

2 Answers 2

9
$\begingroup$

I'll assume the graph is connected, and that you have the clockwise or counterclockwise ordering of the edges around each vertex. Then it's easy, given a directed edge e, to walk around the face whose counterclockwise boundary contains e. So make a list of all directed edges (i. e., two copies of each undirected edge). Pick one directed edge, walk counterclockwise around its face, and cross off all the directed edges you traverse. That's one face. Pick a directed edge you haven't crossed off yet and walk around its face the same way. Keep doing that until you've crossed off all of the edges. (Note that the "counterclockwise" boundary of the exterior unbounded face actually goes clockwise around the outside of the graph.)

If the graph isn't assumed to be connected, then things could be more complicated, since the boundary of a face could have multiple connected components. In that case, you might as well use a standard general-purpose algorithm for computing planar subdivisions. I don't think you lose anything (in asymptotic complexity, anyway) by doing this.

I don't have it in front of me, so I can't tell you with certainty, but I think this is covered in "The Dutch Book" (Computational Geometry: Algorithms and Applications, by de Berg et al.). In any case, that's one of the main references for these types of computations.

$\endgroup$
3
  • 2
    $\begingroup$ I do have Computational Geometry: Algorithms and Applications in front of me and I can confirm that it is covered. The most relevant section is 2.3 Computing the Overlay of Two Subdivisions, and the most relevant pages are p36-37. The book is extremely well written and informative, if you need to solve the problem of the OP, it is highly worth buying. $\endgroup$ Mar 17, 2017 at 23:24
  • $\begingroup$ Can you give an example of a "standard general-purpose algorithm for computing planar subdivisions"? I do not know what you mean by that. $\endgroup$ Sep 15, 2020 at 7:48
  • $\begingroup$ Nice. Thanks for this. $\endgroup$
    – Onye
    Nov 1, 2022 at 16:27
5
$\begingroup$

Hi, there is one such routine in SAGE (http://www.sagemath.org/)

see here: http://www.sagemath.org/doc/reference/sage/graphs/generic_graph.html#sage.graphs.generic_graph.GenericGraph.trace_faces

def trace_faces(self, comb_emb):
    """
    A helper function for finding the genus of a graph. Given a graph
    and a combinatorial embedding (rot_sys), this function will
    compute the faces (returned as a list of lists of edges (tuples) of
    the particular embedding.

    Note - rot_sys is an ordered list based on the hash order of the
    vertices of graph. To avoid confusion, it might be best to set the
    rot_sys based on a 'nice_copy' of the graph.

    INPUT:


    -  ``comb_emb`` - a combinatorial embedding
       dictionary. Format: v1:[v2,v3], v2:[v1], v3:[v1] (clockwise
       ordering of neighbors at each vertex.)


    EXAMPLES::

        sage: T = graphs.TetrahedralGraph()
        sage: T.trace_faces({0: [1, 3, 2], 1: [0, 2, 3], 2: [0, 3, 1], 3: [0, 1, 2]})
        [[(0, 1), (1, 2), (2, 0)],
         [(3, 2), (2, 1), (1, 3)],
         [(2, 3), (3, 0), (0, 2)],
         [(0, 3), (3, 1), (1, 0)]]
    """
    from sage.sets.set import Set

    # Establish set of possible edges
    edgeset = Set([])
    for edge in self.to_undirected().edges():
        edgeset = edgeset.union( Set([(edge[0],edge[1]),(edge[1],edge[0])]))

    # Storage for face paths
    faces = []
    path = []
    for edge in edgeset:
        path.append(edge)
        edgeset -= Set([edge])
        break  # (Only one iteration)

    # Trace faces
    while (len(edgeset) > 0):
        neighbors = comb_emb[path[-1][-1]]
        next_node = neighbors[(neighbors.index(path[-1][-2])+1)%(len(neighbors))]
        tup = (path[-1][-1],next_node)
        if tup == path[0]:
            faces.append(path)
            path = []
            for edge in edgeset:
                path.append(edge)
                edgeset -= Set([edge])
                break  # (Only one iteration)
        else:
            path.append(tup)
            edgeset -= Set([tup])
    if (len(path) != 0): faces.append(path)
    return faces

I also have my own implementation which is an adaptation from the SAGE lib:

  def Faces(edges,embedding)
   """
   edges: is an undirected graph as a set of undirected edges
   embedding: is a combinatorial embedding dictionary. Format: v1:[v2,v3], v2:[v1], v3:[v1] clockwise ordering of neighbors at each vertex.)

    """

    # Establish set of possible edges
    edgeset = set()
    for edge in edges: # edges is an undirected graph as a set of undirected edges
        edge = list(edge)
        edgeset |= set([(edge[0],edge[1]),(edge[1],edge[0])])

    # Storage for face paths
    faces = []
    path  = []
    for edge in edgeset:
        path.append(edge)
        edgeset -= set([edge])
        break  # (Only one iteration)

    # Trace faces
    while (len(edgeset) > 0):
        neighbors = self.embedding[path[-1][-1]]
        next_node = neighbors[(neighbors.index(path[-1][-2])+1)%(len(neighbors))]
        tup = (path[-1][-1],next_node)
        if tup == path[0]:
            faces.append(path)
            path = []
            for edge in edgeset:
                path.append(edge)
                edgeset -= set([edge])
                break  # (Only one iteration)
        else:
            path.append(tup)
            edgeset -= set([tup])
    if (len(path) != 0): faces.append(path)
    return iter(faces)
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.