Adjacency or Edge List to Faces

Question

How to go from an edge list or adjacency list representation of a planar graph to a face list?

For example, with this graph (which is not 0-indexed, oddly enough):

I'd want a list that looks something like this:

[
[1,2,8,7],
[1,2,4,3],
[1,3,5,7],
[2,4,6,8],
[5,6,7,8],
[3,4,6],
[3,5,6]
]

It wouldn't have to be in that format or order, but it should be some kind of list (or set) of all faces. The outer face is included.

For a graph with V vertices (E=O(V) because planar), the algorithm should generate this list in O(V).

Answer 1

You need to generate a planar embedding of the graph. One issue is that often a biconnected graph can generate multiple planar embeddings.

One planarity testing and embedding algorithm is given in the "Planarity Testing by Path Addition" PhD thesis and this solves the problem of generating all possible planar embeddings of a graph (in O(V+E) time and memory for a single embedding for a biconnected graph with V vertices and E edges, and in O(P(V+E)) time and O(V+E) memory to generate all possible unique planar embeddings, where P is the number of permutations of embeddings).

Chapter 5 details the algorithm needed to test a graph for planarity and then to generate a cyclic edge order for each vertex (and also how to iterate to the next permutation of the embedding).

Given a cyclic edge order, you can generate the faces of the graph by taking each edge and following the next clockwise (or anti-clockwise) edge in the cyclic edge ordering as you come to each successive vertex.

Answer 2

The short answer is : you have to actually layout the graph! More exactly, you have to find an embedding of the graph in the plane - assuming that there is one without edge crossings.

So, your embedding above is :

1: [2, 7, 3]
2: [1, 4, 8]
3: [1, 5, 6, 4]
...

which is each vertex with an ordering on its neighbour set. You have to specify if that ordering is clockwise or anti-clockwise, but otherwise that should be all.

Once you have the embedding, it is possible to recover the faces using a combinatorial map. This looks trickier than it really is, although it does involve darts (or flags).

First, break each edge into flags (vertex + half-edge) and make a permutation (sigma in the wiki description) that stores the map. For example, we could label the flags in the same order as the map - then 1: [2, 7, 3] becomes {1->2 : 1, 1->7 : 2, 1->3 : 3} and so on.

For example, a cube (note : removed the middle edge!):

Then calculate alpha (the involution permutation) which just maps flags to the other flag across the edge. Finally, phi is the product of these two permutations, and the cycles of phi gives you the faces.

So, from the phi in the image, we have (1, 6, 24, 19) which is the outer face (note that these are darts, so we consider the vertex it starts from).

Answer 3

As @gilleain mentioned in his answer, you have to actually layout the graph, as there could be multiple layouts if you just give the topology. Here I'll give some algorithmic analysis and then a straightforward solution.

Lemma 1: An edge is involved in at least one face, and at most two faces.

Proof: We're drawing in 2D space so a line splits a plane into two halves.

This means that we can attach a "capacity" to each of the edges, initialized to 2. When we find an face involving an edge, we subtract 1 from it.

As a face is a loop in the planar graph, the problem turns to find loops given the aforementioned constraint.

Lemma 2: If we examine the difference between two valid solutions, they differ in edges that have complementary capacities (1 vs. 2 and 2 vs. 1).

Proof: See the figure.

As a consequence, when you drain the capacity for an edge when finding a solution, you automatically exclude the ambiguity that leads to another solution.

So the straightforward solution is to conduct DFS in the graph to find loops. When you find one, subtract the capacities of the involved edges. When the capacity reaches 0, consider the edge removed when DFS further. Note, when a loop is found, we must check if all the edges within have capacity 1. If so, then this loop must be skipped, as including this loop into our result leads to repeated counting.

def DFS-Tarjan(v, capacities, stack)
    for e in N(v):
        if capacity[e] != 0:
            if stack.contains[e.target] AND NOT all of them have capacity 1:
                output-loop(stack, e.target)
                for e2 in stack:
                    capacity[e2] -= 1
            else:
                stack.push(e.target)
                DFS-Tarjan(v, capacities, stack)
                stack.pop(e.target)
        else:
            pass # capacity drained

def find-faces(g):
    initialize capacities of g.E to [2...2]
    for v in unvisited(g.V):
        DFS-Tarjan(v, capacities, [])

Multiple solutions can be found if you alter the order for DFS. For a single solution, the algorithm is O(V) as each edge is consumed no more than twice.