I have a planar graph, for which I have computed a combinatorial embedding and coordinates in the plane. So all my arcs are now oriented in the plane, respective to their end vertices.
Computing a list of all faces of the graph (as a list of oriented walks along their arcs) is fairly straightforward.
On the other hand, finding a simple way to pick the outer face out of the list of faces does not seem as easy: it is included in the list of faces, but since its orientation is "reversed" (i.e. relative to the outer region, rather than the inside of the graph boundary), all its properties in terms of neighbouring faces are identical to other faces.
Short of using plane coordinates to painstakingly identify the outer nodes/arcs of the graph, is there a more straightforward way to pick the outer face out of the list of faces using the combinatorial embedding (given as a table of arc successors in the oriented plane)?
Edit: Upon reading the comments, I realised that my wording was ambiguous (verging on the incorrect): while I have the combinatorial embedding and would like to use it (or the information derived from it), I also have coordinates derived from a drawing of that graph (hence the plane graph, not simply planar graph), ensuring that there is, indeed, a specific outer face.
What I meant to say is that I am looking for a method that would do more (or rather: less) than just looking at the coordinates of all faces and (for example), compute their orientation.
To be precise, the embedding and plane drawing give me:
- a list of all faces (as an oriented walk of vertices).
- for each arc: the face left and right of it.
- for each vertex: an oriented walk of its ingoing/outgoing arcs (actually, my graph of interest is undirected, but that is probably not very relevant).
Edit 2: Despite the upvotes, the first comment does not really solve much (it essentially boils down to a recursive answer: "in order to find the outer face, use the leftmost vertex, then find the outer face", which isn't as trivial to solve as its commenter seemed to think.
@Zsbán provided what looks like the most efficient and elegant solution. Thanks!