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

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...

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

1. Set

2. Find any cycle in the graph

3. If there are no cycles, there are

4. Remove one of the edges from the cycle (thereby removing one face)

5. set

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

(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

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

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

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

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'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

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

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

posted by phrontist at 4:42 AM on January 16, 2011

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:

posted by Johnny Assay at 7:46 AM on January 16, 2011

- Points 1, 2, 3, and 4 in a horizontal row, in that order. All four of these points connect to point 5 (above the four points) and point 6 (below the four points.)
- Points 1, 3, 2, and 4 in a horizontal row, in that order. All four of these points connect to point 5 (above the four points) and point 6 (below the four points.)

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

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

posted by logopetria at 11:18 PM on January 16, 2011

This thread is closed to new comments.

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]