[SOLVED] Is there an algorithm to determine the faces of a planar graph?

Is there an algorithm to determine the faces of a planar graph?

I'm working on a Java program to analyze graphs in various ways, specifically undirected graphs with weighted edges. I am now trying to, given a planar graph, determine its faces, a.k.a. the enclosed regions of "space" delimited by the graph's edges, but I really can't find an algorithm, or at least a comprehensible one, that could do this and I am struggling to implement one of my one.

Does someone have any idea?

PS : I should note that I do not have a solid basic grasp of graph theory

Solution

The faces of a planar graph depend on having an embedding of a planar graph onto a surface. The issue arises that it is possible for there to be multiple embeddings of a planar graph.

For example:

   ----1----         ----1----      
  /   / \   \       /   / \   \     
 /   /   \   \     /   /   \   \    
2   3-----4   |   2   4-----3   |   
 \   \   /   /     \   \   /   /    
  \   \ /   /       \   \ /   /     
   ----5----         ----5----

The above graph can be embedded in two different ways with different faces for each.

So the first problem is to generate any single embedding; most efficient planarity tests will test planarity by generating an embedding (rather than using a less efficient method such as looking for forbidden minors) so you should be able to use any planarity test for this. The harder problem is to generate all possible embeddings - however, there is a solution for this in Planarity Testing by Path Addition (and contains Java code in the appendices to perform the planarity test, generate an embedding, cycle from one embedding of a biconnected graph to other embeddings and to generate a cyclic edge-order for each vertex for an embedding).

Once you have an embedding, you can represent the graph as a cyclic edge-order for each vertex. So, for the left-hand example:

Vertex Clockwise Edge-Order
------ --------------------
     1              2,5,4,3
     2                  1,5
     3                1,4,5
     4                1,5,3
     5              1,2,3,4

Then to find the faces, you just start at an edge and pick either clockwise or anti-clockwise and keep picking the next adjacent edge in that direction from successive vertices until you return to the starting edge:

Clockwise (2,1) -> (1,5) -> (5,2)
Clockwise (1,2) -> (2,5) -> (5,3) -> (3,1)
Clockwise (1,3) -> (3,4) -> (4,1)
Clockwise (1,4) -> (4,5) -> (5,1)
Clockwise (4,3) -> (3,5) -> (5,4)

And you have the faces (and each edge has been visited twice - once in each direction).