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?
2
$\begingroup$
$\endgroup$
-
1$\begingroup$ How is your graph represented? $\endgroup$ – Louis Mar 28 '16 at 8:49
-
3$\begingroup$ 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? $\endgroup$ – Yuval Filmus Mar 28 '16 at 9:36
-
$\begingroup$ A plane graph is a planar graph with a given embedding. Do you mean a plane graph? $\endgroup$ – Pål GD Mar 28 '16 at 13:08
1
$\begingroup$
$\endgroup$
It depends. If you have a planar embedding, and you want to find faces on it, just pick an edge, and keep walking on the face that's on the 'left' side of the edge when looked at in the direction you were walking. If you want to find a cycle of nodes for which there exists a planar embedding in which those cycles are a face, that's even easier, because in planar graphs, every cycle is a face in some embedding.
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.
answered May 2 '16 at 14:46
-
$\begingroup$ "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 $\endgroup$ – Smylic Nov 21 at 18:39
-
1$\begingroup$ @Smylic What a good find! Then the answer is quite wrong, and does not in fact find a face. Thank you. If only there were a way to downvote my own answer. I'll think on how to repair it. $\endgroup$ – Lieuwe Vinkhuijzen Nov 22 at 9:29
