# 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.
• "every cycle is a face in some embedding" This is really false statement. Even if we consider only simple cycles, it is still false. Even if we consider only triangles, it is still false. Just an example: $K_5 - e$, the graph that appears after deleting an arbitrary edge from $K_5$. Three vertices in $K_5 - e$ are universal and therefore form a triangle. This triangle can't be a face, because in this case both other vertices should be together either outside or inside this triangle, that is clearly impossible. However the graph is clearly planar – Smylic Nov 21 at 18:39