Join 3,572 readers in helping fund MetaFilter (Hide)


Faces
January 15, 2011 7:36 PM   Subscribe

Newbie Graph Theory: How can I find all the faces of a planar undirected graph? Or, what I think is equivalent, all of the chordless cycles (cycles in which no two nodes are connected by any path other than a subset of the cycle) .

I'm fairly sure this is wrong, as it will find cycles whose elements are connected by non-cycle paths if those connections aren't direct.

I have a feeling spanning trees are involved...
posted by phrontist to Science & Nature (14 answers total) 1 user marked this as a favorite
 
Do you already have the coordinates of each point in a planar representation, or do you just have a list of vertices and edges? If it's the former, you can find the faces geometrically by starting at a point, following a random edge, and then "taking a right" when you reach the next vertex, continuing to do so until you reach the original point again; you've just described a face. You can avoid doing extra work when enumerating all of them by noting that traversing a given edge in a single direction only ever has to be done once (although traversing it in the other direction will be part of another face unless you're on the edge of the graph).

If you don't have the coordinates of the vertices, I suppose you could "planarize" it first (there must be an algorithm for this) and then follow the above directions. It's hard for me to imagine doing it directly with the (V,E) representation because it seems that it would be super-hard to reason about the geometry of it when the representation is that abstract.
posted by dfan at 8:11 PM on January 15, 2011 [2 favorites]


If you know the graph is planar, it seems like the following should work:

1. Set n = 0
2. Find any cycle in the graph
3. If there are no cycles, there are n faces, so exit
4. Remove one of the edges from the cycle (thereby removing one face)
5. set n = n + 1
6. Goto step 2
posted by Blue Jello Elf at 8:17 PM on January 15, 2011


On further reflection, I imagine you must have the coordinates already, because otherwise many graphs have an ambiguous "planarization" and the resulting faces would be different (e.g., make a triangle A-B-C, then add edges B-D and C-D; D could either be inside or outside the triangle). So the procedure in the first paragraph seems like the way to go.

(By the way, I think you may end up with one spurious "face" that is actually the outer boundary of the entire graph, so be careful to discard that one...)
posted by dfan at 8:19 PM on January 15, 2011


Blue Jello Elf, are you just counting the number of faces? The original question seems to want to identify them.
posted by dfan at 8:20 PM on January 15, 2011


Also, I think you can make it easier to find cycles by having a function that removes any vertex with a single edge as long as there are any vertices with a single edge, thereby ensuring that all the remaining vertices must necessarily be part of a cycle.

function CountFaces( graph )
1. RemoveStrayVertices( graph )
2. set n = 0
3. while( graph.edges.count > 0 )
 3.1. graph.remove( graph.edges[0] )
 3.2. set n = n + 1
 3.3. RemoveStrayVertices(graph)
4. return n

function RemoveStrayVertices( graph )
1. set m = 0
2. foreach( vertex in graph )
 2.1. if (vertex.edges.count == 1)
  2.1.1. graph.remove(vertex)
3. if m > 0 goto 1
4. return
posted by Blue Jello Elf at 8:26 PM on January 15, 2011


By the way, if you do want to just count the number of faces, it's E - V + 2 (or + 1 if you don't want to count the infinite "face" forming the boundary of the graph).
posted by dfan at 8:38 PM on January 15, 2011


Warning - math theory has an alarmingly short half-life in my brain, so please don't take any of this as gospel. (and I'm pretty sure that my explanations below are way too informal/fuzzy to have gotten full credit :0 )

First - in my graph theory course we counted the infinite external face as one of the graph's faces. dfan mentioned this a few times, and it's why the actual embedding of the graph doesn't matter for counting (or even enumerating) the faces. There's an actual theorem that says that you can choose any face of a planar graph to be the outer face in your embedding.

dfan's formula is correct - #faces = #edges - #vertices + 2.
you're also correct that one explanation of it involves spanning trees. :-)
Recall that a spanning tree of a graph has #vertices - 1 edges, and that adding any edge to the spanning tree will create a unique chordless cycle. So - there are #edges - (#vertices -1) edges to be added to your spanning tree, each of which gives you a unique face. When you add in the outer face, you get dfan's formula.
posted by Metasyntactic at 8:51 PM on January 15, 2011


Aaah - forgot to add in an algorithm outline for actually enumerating the faces.
I'm too tired to finish this / prove correctness/what have you right now, but I'd start with something like:

* compute spanning tree T of graph G
* for each e in G but not in T
** let p1 and p2 be the endpoints of e
** find the unique path between p1 and p2 in T. Since T is a spanning tree, this unique path is guaranteed to exist.
** add [pe] to your list of cycles

Note that your list of cycles aren't guaranteed to be chordless at this point - for example, in the graph:
._._.
|_|_|

you could have the spanning tree:
._._
._._|

and the cycles ffrom the spanning tree would look like
._.
|_| and
._._.
|_._|

but clearly, on the full graph, the 2nd one has a chord.
... So you need to find a way to prune them. maybe something like:

while there are candidate cycles in your list,
* for each c in your list of cycles (where the cycles are just lists of vertices at this point)
** find all edges with both endpoints in c. let g2 be the subgraph of G induced by these edges.
** if the number of such edges = number of nodes in c
**** this is a face, and needs no modification
** otherwise
**** compare to list of faces. If one of the known faces is a subgraph of g2, find way to remove some of the edges from g2, and put the resulting (shorter) potential cycle back into your queue

I think you can show that at each step your list of potential faces gets shorter by at least one, so the alg terminates (maybe by directly integrating this into the first cycle-finding alg?)

Don't forget to find and add in the external face.

blargh. I hope sombody will come along with a more complete and more elegant solution for you =)
posted by Metasyntactic at 9:22 PM on January 15, 2011


I think dfan has the right answer. If you don't have a planarization, you can't answer this question because although the number of faces is fixed, their identity isn't. If you have a planarization in the form of coordinates for each vertex, then it's easy to use a wall-following algorithm to identify each face. If you have a unique planarization specified in some other way, then you need to clarify.
posted by hattifattener at 9:59 PM on January 15, 2011


Ok - i was wrong about enumerating faces - I'd gotten plane graphs vs. planar graphs mixed up ...
posted by Metasyntactic at 10:27 PM on January 15, 2011


I'd been banging my head against the wall trying to do it with just the adjacency information even though I've already got a planarization. The wall following solution will do just fine. Thanks!
posted by phrontist at 4:42 AM on January 16, 2011


It's hard for me to imagine doing it directly with the (V,E) representation because it seems that it would be super-hard to reason about the geometry of it when the representation is that abstract.

Out of curiosity though, can you do it with just the (V,E) representation? Is the question even coherent without locations for the points? It seems to be.
posted by phrontist at 4:48 AM on January 16, 2011


I don't think the question is well posed without the planarization. Draw the following graphs:These graphs both have the same adjacencies, but there's a face whose corners are (1, 5, 2, 6) in the first graph and not in the second.
posted by Johnny Assay at 7:46 AM on January 16, 2011


The adjacency information will let you work out the set of cycles of the graph. In a given planarization the faces will form a basis for the set of cycles. So given the set of cycles, you can find a subset that form a basis, and take these as your faces -- I think this always gives a valid planarization, but I'm not sure.

However, a graph can (I think) have multiple non-isomorphic planarizations, so there's no sense in which any particular cycle of a graph given in (V,E) form is a face -- it'll be a face in some planarizations and a compound cycle in others.
posted by logopetria at 11:18 PM on January 16, 2011


« Older Why won't my Sansa Clip play m...   |  How can I overcome my anxiety ... Newer »
This thread is closed to new comments.