Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a graph $G$ with a list of edges $E$, all the edges can form cycles, as shown below:

All the coordinates for the vertex $V$ are known.

Wat is the algorithm to find all the faces $F$? For the example above, there are 4 such faces, as indicated by the looping arrow.

Update: Why is it that the algorithm to find the face in the case without coordinate is different from the one with coordinates? Simply because by specifying the coordinates there is a unique set of faces, and without coordinates there could be sets of faces that are topologically equal. See the diagram below:

Update 2: Clear up the terminology

UPdate 3: It is suggested that I construct a cyclically linked list at each vertex, sorted according to the angles made between the incoming edge and the outgoing edge. Then one would just have to continue along the edge, but I afraid this algorithm doesn't work with the so called butterfly graph. Consider this graph:

Assume that we start at $e_1$, and the arrow denotes the direction of the movement. If we take the left turn as our orientation then we would be visiting $v_1$ twice before completing a cycle-- and the cycle is not really a cycle.

share|improve this question
3  
I find quite a few things that seem relevant in a Famous Web Search Engine –  Ross Millikan Oct 28 '10 at 4:46
    
@Ross, from what I know all those algorithms are only applicable for the case where the vertices coordinates are not known. –  Graviton Oct 28 '10 at 6:13
    
Duplicate: stackoverflow.com/questions/4023310/… –  KennyTM Oct 28 '10 at 6:48
    
@KennyTM, the reason why I ask it here is because I didn't find good answers there. These are separated forum and different people might have different take on the same issue. So it's not fair to call this question as a dupe of other question. –  Graviton Oct 28 '10 at 7:04
3  
@Ngu Soon Hui: I was not trying to be funny. It is clear from your latest update that you are not trying to find what most people call a minimum cycle bases, but a list of the boundaries of the faces in a planar embedding of a planar graph. The difference between the two things is not that you know or not know the coordinates of the vertices! The difference lies in what you want to do with the graph. –  Mariano Suárez-Alvarez Oct 28 '10 at 17:17

3 Answers 3

up vote 9 down vote accepted
+50

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.

share|improve this answer
    
@hardmath, thanks for the detail answer! You have any reference on this matter, i.e, on cyclically linked "list" that goes around the vertex thing? I would have to give your answer a good, long read and I'll need as much background as possible for this. –  Graviton Dec 21 '10 at 15:10
    
Also, for step 2 of the algorithm, how to Consult the cyclically linked list of edges at that vertex to determine the next edge? Remember at this point, we don't even know what are the cycles ( faces) yet ( in fact to get the cycles is our goal!), so it doesn't really make sense to say that we can sort sort the edges around each vertex into a cyclically linked "list" that goes around the vertex in the counterclockwise direction, am I right? –  Graviton Dec 21 '10 at 15:16
    
A cyclically linked list is a data structure, like a list except that instead of reaching the end of the list it loops back around to the beginning. It is not the same as the "cycles" you want to find, it is much easier. Take a vertex of the graph. It has some edges "incident" to it, if the graph is connected. I'll find a reference for cyclically linked list, but you have to know what order the edges that a vertex has appear in, and how to sort them as they appear going counterclockwise around the vertex in the plane. It's part definition of the planar embedding of the graph. –  hardmath Dec 21 '10 at 15:41
    
@hardmath, btw, is there a name for the algorithm that you and @Mariano describe? –  Graviton Dec 21 '10 at 15:55
    
Thank you for the exegesis! :) –  Mariano Suárez-Alvarez Dec 21 '10 at 16:05

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.

share|improve this answer
    
sorry for the late reply! you said done easily by sorting the edges incident to each vertex cyclically, can you please elaborate on this? –  Graviton Dec 20 '10 at 6:58
1  
I've two questions here: First, how do you sort the edge cyclically. Second, how is it that sorting the edge cyclically leads to face determination? –  Graviton Dec 20 '10 at 11:26

This was my project not so long ago.

I solved it in more than one way. But I will present you the easiest of the methods I used. Use quick fill inside of a region. Then find the lines that border the region.

It fails in certain situations, however, in most cases, those situations are not that serious anyway. If this method fails for you, post back and I will share the other methods that I used.

share|improve this answer
1  
quick fill inside a region-- not sure what do you mean here, how you do quick fill? And what are the other methods? –  Graviton Dec 22 '10 at 6:57
    
Sometimes Google is a good searching tool. Obiously you cannot search. Once you try this and it fails, Ill explain the other methed. But for starters, you need to convert from vector to raster, apply quickfill on the raster, and find a way to determine which vectors are around the filled region. codeproject.com/KB/GDI/QuickFill.aspx –  picakhu Dec 22 '10 at 17:59
    
(1) While this is a nice trick, I understand the confusion of Ngu Soon Hui, because you omitted the first important step in your answer: convert the plane graph to a raster image. (2) As you said, this trick does not always work. I would hesitate to say “those situations are not that serious anyway” because whether it is a serious shortcoming or not depends on the application. –  Tsuyoshi Ito Dec 23 '10 at 10:51

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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