Find all cycles (faces) in a graph

Solution 1:

In your previous question better use was made of graph theory terminology: you refer to the graph as planar and to a cycle basis.

Assuming you understand those terms, perhaps I can point out how Mariano's answer builds on the earlier problem. In fact here you asked, "Why is it that the algorithm to find the face in the case without coordinate is different from the one with coordinates?" Although this is probably meant rhetorically to explain your assumption "All the coordinates for the [vertices] are known," it's important to point out that "faces" you've asked to find will depend on where the edges are as well as where the vertices are.

Let's illustrate with the complete graph on four vertices $K_4$. Define planar coordinates for the vertices to be corners of the unit square {(0,0),(1,0),(1,1),(0,1)}. There will be four edges, but we cannot take all of them to be straight line segments in the plane, since doing so produces an intersection (something a planar embedding of graph does not allow).

In fact depending on how you connect the vertices, you will get different faces. Draw two squares (with four edges each), and connect one pair of "diagonal" vertices inside one square and the other pair inside the other square. Now complete both graphs with an outside edge that connects the remaining diagonal pairs, looping over the square in one case and under the square in the other. Two (or more) cases with different arrangments of "faces".

The point is that knowing a planar embedding well enough to make the "faces" cycle basis you're looking for unique requires you to "know the coordinates" of the edges as well as the vertices.

Mariano's answer focuses on the edges. This has the nice effect of allowing us to count each edge as belonging to exactly two cycles or faces, once for each direction that the edge is travelled. [No such simple statement will hold for the number of faces that a vertex appears in.] However to make that "two cycles per edge" work, we must include the "unbounded face" or the cycle that runs all around the outside of the planar graph. In the simplest case, a triangle say, we have a cycle that goes clockwise around it (following the direction you've used in your diagrams at top). To get each edge appearing twice, once in each direction, we need to get a counterclockwise cycle. You can think of one being the "finite" face bounded by the triangle, and the other being the face corresponding to the unbounded region outside the triangle.

When you ask Mariano to tell you how to "sort the edge[s] cyclically," I guess there are two aspects of this. One is to understand what he means by that, and the other is to connect this task with how you "know the coordinates" of the graph including its edges.

What Mariano means is just to know, when we arrive at a vertex along one "inbound edge", what will be the right "outbound edge" to take next? Let's suppose you want to construct all the "finite" faces going in the clockwise direction, as in your diagrams. Then you would need to sort the edges around each vertex into a cyclically linked "list" that goes around the vertex in the counterclockwise direction. This "list" wraps around; it has no specific beginning or ending edge. It also does not distinguish the directions of travel along the edge. It just tells us, for all the edges at a given vertex, which follows which going counterclockwise around the vertex.

Now we can elaborate Mariano's solution to your question. For each edge and each direction of travel along that edge, build a cycle by this algorithm:

Algorithm FollowYourNose
(1) Follow the given edge in the given direction to its end vertex.
(2) Consult the cyclically linked list of edges at that vertex to determine the next edge.
(3) Repeat steps (1) and (2) until you return to the original edge.
(4) Stop. You have built a cycle that uses the given edge and given direction.

When you've done this for each edge and each direction, you will have a list of cycles that contains duplicates. If a cycle contains $k$ edges, you will have built that same cycle $k$ times. Discard the duplicates, leaving just one copy of each cycle. [If it's important for performance reasons, we could keep track of which edges have been travelled in which directions and preemptively avoid creating the duplicates.]

You will then have one copy left of the cycle that corresponds to the unbounded face, the outside of the planar graph. You want to remove that also. Where all the cycles that correspond to the bounded faces are going in the clockwise direction, the cycle that corresponds to the unbounded face goes in the counterclockwise direction. In fact it is algebraically minus the sum of all the clockwise/bounded face cycles.

Added: A cyclically linked list (or some would write, cyclic linked list) is a special case of a linked list. It means that the linked list comes around in cycle or loop. No confusion with the "cycles" of the graph is intended here. We are simply asking for some concrete way to systematically determine how to continue a path in the graph with each vertex we come to. An informal description would be to say "bear right at each intersection". Doing so will of course take us around the block in terms of ordinary street traffic, and it has a similar effect in navigating a planar graph.

What Mariano proposed was to answer the question of "which way to go" by sorting the edges that are incident to each vertex in an order corresponding to the angles at which they reach the vertex. Think of standing in a intersection (vertex) of two or more streets (edges). List them (the edges or streets) in the order they appear as you turn counterclockwise through one revolution, and use that list/ordering in the algorithm outlined by Mariano, so that when you enter an intersection (vertex) on one street (edge), you leave along the next one on the list (bear right!).

We should also be a bit careful about the kind of planar graph that the algorithm applies to. If you are willing to accept certain degeneracies, then planar graph is good enough. But consider the case of a single edge connecting two vertices. What is the face?

If you wish to avoid such degeneracies, then assume a simple planar graph that is 2-connected. What 2-connected means is that the graph is connected and remains connected even after any one edge is removed. "Simple" means that there are no "self-edges" (edge that connects a vertex to itself) nor multiple edges connecting a single pair of vertices.

Regarding Update 3: It is not suggested that you sort edges "according to the angles made between the incoming edge and the outgoing edge." You are asked to make for each vertex a list of the edges ordered going counterclockwise around that vertex (a circular list if you will), without any regard to incoming or outgoing. In your butterfly graph there is only one vertex with more than two edges, so only the list for that vertex requires care in sorting.

Worked Examples Involving Butterfly Graph

Let's consider first a planar embedding of the butterfly graph similar to what was once part of the Question:

   v2    v3    +e1: (x,v1)  -e1: (v1,x)  
    |\   /|    +e2: (x,v2)  -e2: (v2,x)  
    | \ / |    +e3: (x,v3)  -e3: (v3,x)  
    |  X  |    +e4: (x,v4)  -e4: (v4,x)  
    | / \ |    +e5: (v1,v2) -e5: (v2,v1)  
    |/   \|    +e6: (v3,v4) -e6: (v4,v3)  
   v1    v4  

I've used plus and minus signs to (arbitrarily) assign directions for each of the six edges. Only the center vertex x has more than two incident edges, so I'll be explicit about ordering the edges (without regard to incoming or outgoing direction) in counterclockwise order around x:

...e4,e3,e2,e1,e4,...

It should be clear that this is a circular list, that it repeats, looping through the same order of edges over and over again, which in data structures we would represent as a cyclically linked list. Nothing more than the standard apparatus for linked lists is required to do this. One simply makes the final node of the linked list point back to the first node of the linked list, and voila, a cyclically linked list. But let's not confuse the details of the implementation with the details of the algorithm. All that the algorithm requires is how to find the next edge at a vertex which is counterclockwise from a given edge at that vertex. A cyclically linked list does that function, in that we would search the list linearly for the given edge at the given vertex, then take the next edge on the list.

Since there are six edges, there are twelve directed edges, and thus we will apply the algorithm FollowYourNose twelve times (once for each directed edge). Each time we will get a cycle (a loop on edges). Cycles may visit a vertex more than once but will never use an edge more than once (assuming the planar graph is simple and 2-connected). However the twelve results will contain duplicates. Once the duplicates are removed, there are just three unique cycles left:

[+e1,+e5,-e2]

[+e3,+e6,-e4]

[-e1,+e4,-e6,-e3,+e2,-e5]

It appears from the diagrams provided in the Question, that "faces" are meant to be the bounded components of the plane after the edges of the embedded graph are removed (thereby disconnecting the plane into one unbounded and finitely many bounded components). So we should remove from the list of three cycles above that one which corresponds to the boundary of the unbounded component.

This distinction can be made algorithmically on the clockwise or counterclockwise orientation of the cycles. The cycles that give "faces" are going clockwise around their bounded components. The cycles which is a boundary of the unbounded component goes counterclockwise. In this case it is the third cycle that should be discarded.

To illustrate how the distinction is made on the basis of clockwise orientation, and not on some other criterion such as which cycle has greatest length, let's look at another embedding of the butterfly graph:

           _ x _              +e1: (x,v1)  -e1: (v1,x)  
         _/ / \ \_            +e2: (x,v2)  -e2: (v2,x)  
       _/  /   \  \_          +e3: (x,v3)  -e3: (v3,x)  
     _/   v2___v1   \_        +e4: (x,v4)  -e4: (v4,x)  
    /                 \       +e5: (v1,v2) -e5: (v2,v1)  
   v4_________________v3      +e6: (v3,v4) -e6: (v4,v3)  

I have taken care to make the labelling of the edges with respect to the vertices the same here, as well as the orientations of the two 3-cycles in the plane the same. The algorithm will now produce a different result based on the change in how the edges incident to vertex x are ordered going counterclockwise around that vertex:

...e4,e2,e1,e3,e4,...

Again we will apply algorithm FollowYourNose to each of the twelve directed edges and obtain twelve cycles, including duplicates. After eliminating duplicates the following three cycles remain:

[+e1,+e5,-e2]

[+e3,+e6,-e4,+e2,-e5,-e1]

[+e4,-e6,-e3]

It is left to the reader to verify which of these has counterclockwise orientation and that it is not the longest of the three cycles. The one with the counterclockwise orientation is the "outermost" and thus the boundary of the unbounded component of the plane\graph.

Solution 2:

Consider your graph is planarly embedded in the plane. And think of edge unoriented edge as a pair of oriented arcs in opposite directions.

Pick one oriented arc $a$. There is a unique face whose boundary, when drawn in counterclockwise direction, "contains" $a$, and in that boundary $a$ is followed by a well-defined arc $b$.

To construct the faces, it is enough to be able to decide for each $a$ what the corresponding $b$ is. This can be done easily by sorting the edges incident to each vertex cyclically.