Finding outer face in plane graph (embedded planar graph) 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!
First, suppose that your arcs are embedded to the plane as straight lines.  Then, the following three step algorithm works.

First, compute the leftmost vertex (as David Eppstein suggested).  This vertex will be on the unbounded face.

Second, among the arcs from that vertex, find the one whose slope is largest. This arc will be a side of the unbounded face.  (You must consider the slope; taking the arc with the leftmost destination vertex wouldn't work.  You may have to handle the case when this vertex is isolated somehow.)

Thirdly, take the face on the left hand side of this arc.  That face is the outer face. 

If the edges aren't embedded as straight lines, then you need some extra information about the embedding.  Indeed, in any plane graph (with at least one cycle), you could just take an edge of the outer face and lift it around the whole embedding.  This changes the outer face, but doesn't move the vertexes, and doesn't change the cyclical orientation of arcs from the vertexes.  

In particular, if the edges are open polygons given with the coordinates of the list of inner vertexes, then divide each such edge to a path and run the previous algorithm in the subdivided graph.  This may choose such an internal vertex in the first step.