Finding one face in planar graph

Given a planar graph (represented using adjacency lists) we want to find a set of vertices which are around one (random) face. We know that the graph contains at least one triangle.

How do we find such a face?

• How is your graph represented? – Louis Mar 28 '16 at 8:49
• What do you mean by face? The faces depend on the planar embedding. Do you have a particular planar embedding in mind, or are you just interested in a set of vertices which are a face in some embedding? – Yuval Filmus Mar 28 '16 at 9:36
• A plane graph is a planar graph with a given embedding. Do you mean a plane graph? – Pål GD Mar 28 '16 at 13:08

Here's a simple algorithm for finding a cycle, but you can think of your own one. Suppose you have a graph that you know is planar, and you want to find a face. Start at some vertex $v$ and perform a breadth-first search. In iteration $k$, you find the vertices at distance $k$ from $v$ and for each vertex at distance $k$ that you add, you count how many nodes at distance $k-1$ were connected to that node. If there is just one, then continue. Otherwise, if two nodes at distance $k-1$ are connected to a node $w$ at distance $k$, then you have found a cycle in the graph (it is possible that you count three or more, in that case, select two). Node $w$ lies on a face in the graph, in some planar embedding of the graph. It may lie on the same face as $v$, but not necessarily, for example, you can have a cycle with a tail, and you accidentally started in the tail.
To find a face, backtrack from $w$ within the nodes that you explored so far with your breadth-first search: first, two nodes $x_1, x_2$ at distance $k-1$ (like I described above). Then, in each iteration, for $x_1$, find the node $x_1'$ which is connected to $x_1$ and is at distance $k-2$ from $v$ (why is there guaranteed to be only one? Because we identified $w$ as most nearby node with two paths leading to it from $v$), and repeat this until at some distance $d$ you find that your $x_1$ ancestor and your $x_2$ ancestor are the same node $y$.
You now have a face! That is, a cycle for which there is some planar embedding. The face has $w$ on one side, $y$ on the other side, and they are connected with two paths. One path is the series of $x_1$ nodes that you just found, and the other is the series of $x_2$ nodes. If you found $y=v$, then $v$ is on the face. You are not guaranteed to find a face with $v$ on it, but are other algorithms that find one if there is one. I can modify this algorithm to do that, and I'm sure you can too.