<p>First, suppose that your arcs are embedded to the plane as <strong>straight lines</strong>.  Then, the following three step algorithm works.</p>

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

<p>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.)</p>

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

<p>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.  </p>

<p>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.</p>

CC BY-SA 3.0
2014-11-28T01:37:08.447Z
This is definitely a huge improvement over my idea (somehow did not occur to me to simply go *up*, as well as left, and be done with it).

One small comment: I am not sure I see what the problem could be with taking the target vertex (connected to $v_1$) that is 1. above (non strictly) $v_1$ and 2. left (non strictly) of $v_1$. Not dealing with angles would make the whole thing a lot easier. Not sure what you mean by an "isolated" vertex... Do you have a specific counter-example in mind?
Dave
CC BY-SA 3.0
2014-11-28T02:35:44.017Z
Never mind my previous comment, I think I see what you meant by "isolated vertex" and how it would pose a problem (the case where the leftmost is also the uppermost?)... But at any rate, perhaps the phrase "leftmost angle arc" needs a better definition: it seems to me that it should be the arc with the largest (direct) angle from vector [0, -1] (vertical, below the vertex). Does that seem correct to you?
Dave
CC BY-SA 3.0
2014-11-28T07:57:59.673Z
I changed the description of the angle thing, the previous description was too complicated.
Zsbán Ambrus
CC BY-SA 3.0
2014-12-01T04:28:25.103Z
Replaced "angle closest to vertical" with "maximum slope". Angles are evil (and numerically unstable).
Jeffε
CC BY-SA 3.0
2014-11-27T18:11:31.673Z
2014-12-01T04:27:42.483Z
2014-12-01T04:27:42.483Z
Zsbán Ambrus
<p>It appears to me that the best way to determine the unbounded face is to compute the signed area of each face. All faces have one sign, and the unbounded face has the opposite sign. You can use the formula for the area of a polygon, given its vertices, from</p>

<p><a href="https://www.seas.upenn.edu/~sys502/extra_materials/Polygon%20Area%20and%20Centroid.pdf" rel="nofollow noreferrer">https://www.seas.upenn.edu/~sys502/extra_materials/Polygon%20Area%20and%20Centroid.pdf</a></p>

<p>or, use the Java example below.</p>

<pre><code>public static double area(Point[] Vertex)
{
    int i, j, n = Vertex.length;
    double area = 0;

    for (i = 0; i &lt; n; i++)
    {
        j = (i + 1) % n;
        area += Vertex[i].getX() * Vertex[j].getY();
        area -= Vertex[j].getX() * Vertex[i].getY();
    }

    area /= 2.0;

    return (area);
}
</code></pre>

CC BY-SA 4.0
2020-03-30T19:13:41.407Z
2020-03-30T19:13:41.407Z
Para Parasolian
<p>As you are computing a list of all faces of the graph as a list of oriented walks along their arcs (as you've written) you could compute the area of the face (polygon) efficiently as is suggested in the second algorithm here (since you have plane coordinates of the vertices): <a href="https://stackoverflow.com/questions/451426/how-do-i-calculate-the-surface-area-of-a-2d-polygon/717367#717367">Area of polygon</a>. The face with largest area should be the outer face of your graph.</p>

<p>About using information only in the combinatorial map, I think Noam Zeilberger is right about that they can be embedded in different ways on the plane. More information about this may be here: <a href="http://liris.cnrs.fr/Documents/Liris-5009.pdf" rel="nofollow noreferrer">Polynomial Algorithms for Subisomorphism of nD Open Combinatorial Maps</a></p>

CC BY-SA 3.0
2014-11-27T07:52:08.960Z
This would indeed work, but rather cumbersome (and potentially quite time-consuming, even if it remains O(n))... However, this inspired me toward a working solution that required a lot less effort, so thanks for pitching in!
Dave
CC BY-SA 3.0
2014-11-26T14:32:37.920Z
2014-11-26T14:32:37.920Z
2017-05-23T12:40:09.333Z
kudy
<p>A non-trivial method can be to calculate the convex hull of the vertices.
(This can only be used if the planar graph generated has a convex outer face, which is most likely the case for most of the graph drawing softwares.)</p>

<p>It seems to be an overkill though but it will give you the face exactly in form of a sequence of vertices given the coordinates of the vertices.
It takes $O(n\log n)$ time to find it. You can use the standard LEDA library to find it easily using its 
<a href="http://www.algorithmic-solutions.info/leda_guide/geo_algs/convex_hull.html" rel="nofollow noreferrer">subroutine</a>.</p>

<p>However it can also be performed in linear time. Please refer to <a href="https://stackoverflow.com/questions/14735164/convex-hull-in-on-time">this</a>.</p>

CC BY-SA 3.0
2014-11-27T07:48:10.740Z
Yes, convex hull was my go-to solution. The problem is that in addition to having non-linear complexity (which would worsen the overall complexity of what I am trying to do), it depends on the "niceness" of the graph drawing algorithm: a plane graph could perfectly have concave angles on its outer boundary.
Inspired by some other contributions, I have figured a solution that is a bit more straightforward (and definitely O(n)). I will post it and maybe someone can improve it or critique it.
Dave
CC BY-SA 3.0
2014-11-27T07:11:05.787Z
2014-11-27T07:11:05.787Z
2017-05-23T12:40:09.333Z
sbzk
<p><strong>Edit:</strong> actually, step 2 is wrong (see comments). Anyway, the accepted answer solves this much more elegantly.</p>

<p>Since there does not seem to be any (straightforward/simple) answer so far, I thought I would post what I came up with, with inspiration taken from @DavidEppstein's comment and @kudy's answer:</p>

<p>Figuring out the leftmost/rightmost point indeed seems to be a good start. However, from there, @DavidEppstein's idea is unfortunately not applicable (there is no straightforward way to know the face "left of a vertex" in the plane). Instead this is what I do:</p>

<ol>
<li><p>Find rightmost point $v_1$ of graph in the plane.</p></li>
<li><p>Find rightmost point $v_2$ connected to $v_1$.</p></li>
<li><p>Take the two faces bordering edge [$v_1$,$v_2$]. Let the longer one (in number of vertices) be $F_a$ and the other one $F_b$.</p></li>
<li><p>Pick an arc $A_a$ in $F_a$ that is not in $F_b$ (we know there is such an arc since the two faces cannot be identical and $F_a$ is longer than $F_b$).</p></li>
<li><p>If the middle of $A_a$ is inside the polygon formed by the vertices of $F_b$ in the plane, $F_b$ is the outer face, otherwise $F_a$ is.</p></li>
</ol>

<p>I welcome any comment and improvement to the method!</p>

CC BY-SA 3.0
2014-11-27T14:32:02.090Z
I think this won't work as is, because v_2 may be a vertex not on the outer face.  It can be fixed to work though.
Zsbán Ambrus
CC BY-SA 3.0
2014-11-28T01:24:17.467Z
Are you certain? We know that $v_1$ is on the outer face. Therefore if $v_2$ is not, it would be inside the outer face and there would be a vertex connected to $v_1$ that is more to the right than $v_2$...
Dave
CC BY-SA 3.0
2014-12-01T13:12:34.463Z
(Sorry, let me try again.) No, this doesn't work; the righmost neighbor of the righmost vertex can be in the interior. Imagine a tiny tiny horizontal edge to the left of the rightmost vertex.
Jeffε
CC BY-SA 3.0
2014-12-02T03:25:09.667Z
@JɛﬀE: thanks for the clarification: you mean e.g. a horizontal edge left of $v_1$ while the real outer edges go farther left (the 'tiny tiny' part kind of threw me off). Indeed, that's a problem. I guess there is no way around looking at angles/slope in the way Zsban suggested.
Dave
CC BY-SA 3.0
2014-11-27T08:04:30.480Z
2014-12-02T03:28:33.813Z
2014-12-02T03:28:33.813Z
Dave
<p>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.</p>

<p>Computing a list of all faces of the graph (as a list of oriented walks along their arcs) is fairly straightforward.</p>

<p>On the other hand, finding a simple way to pick the <strong>outer face</strong> 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.</p>

<p>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)?</p>

<p><strong>Edit:</strong> 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 <em>also</em> have coordinates derived from a drawing of that graph (hence the <em>plane</em> graph, not simply planar graph), ensuring that there is, indeed, a specific outer face.</p>

<p>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. </p>

<p>To be precise, the embedding and plane drawing give me:</p>

<ul>
<li>a list of all faces (as an oriented walk of vertices).</li>
<li>for each arc: the face left and right of it.</li>
<li>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).</li>
</ul>

<p><strong>Edit 2:</strong> 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.</p>

<p>@Zsbán provided what looks like the most efficient and elegant solution. Thanks!</p>

CC BY-SA 3.0
2014-11-26T08:31:51.600Z
Is there a reason you can't just look at the face to the left of the leftmost vertex?
David Eppstein
CC BY-SA 3.0
2014-11-26T12:14:06.823Z
@DavidEppstein maybe I misunderstand what you mean but I don't think "face to the left of the leftmost vertex" is well-defined: a face can be to the left of an oriented edge, not a vertex.
Noam Zeilberger
CC BY-SA 3.0
2014-11-26T12:22:42.777Z
@Dave by "combinatorial embedding" do you mean combinatorial map (https://en.wikipedia.org/wiki/Combinatorial_map)?  Then no, you cannot determine the outer face just from that data, since a planar combinatorial map can be embedded in different ways on the plane so that any face becomes the outer face.
Noam Zeilberger
CC BY-SA 3.0
2014-11-26T12:25:10.517Z
In general it makes sense to talk about the outer face (or "root face") of a *rooted* combinatorial map, that is, a combinatorial map with a distinguished dart chosen as the "root dart".  Then the outer face is usually defined as the face to the right of that dart.
Noam Zeilberger
CC BY-SA 3.0
2014-11-26T16:38:28.660Z
He says he has coordinates in the plane. So the leftmost vertex is well defined (the one with the smallest x coordinate) and the face to its left is well defined (the one that you move into if you reduce the x coordinate value even more).
David Eppstein
CC BY-SA 3.0
2014-11-26T21:02:32.100Z
@DavidEppstein I think you might be making additional assumptions which aren't in the usual definition of "embedded plane graph"/"plane map" (e.g., in general the graph can contain loops and multiple edges). Have a look at the two planar maps in the middle of page 2 of http://www.labri.fr/perso/zvonkin/Research/belyi.pdf. Does your criterion correctly identify the outer face?
Noam Zeilberger
CC BY-SA 3.0
2014-11-27T01:42:40.333Z
I am perfectly aware of the definition of a combinatorial map, but unlike you I am also reading the first sentence of the question, which says "and coordinates in the plane". If we have these coordinates, why not use them?
David Eppstein
CC BY-SA 3.0
2014-11-27T02:04:27.320Z
what I'm saying is that identifying the leftmost vertex does not let one determine the outer face, and that the two maps on p.2 of the article I linked to above are both counterexamples to your suggested algorithm. The map on the left has two faces incident to the leftmost vertex and no criterion as far as I can tell (regardless of knowledge of vertex coordinates) for determining which face is "to the left".  The map on the right has only one face incident to the leftmost vertex, but it is actually *not* the outer face.
Noam Zeilberger
CC BY-SA 3.0
2014-11-27T04:34:45.530Z
@DavidEppstein: I do have coordinates, which means I can indeed find the leftmost vertex very easily, but I cannot see any method which would give me the *face* left of that vertex in any trivial (or even easy) way. The faces I have are defined as walks of vertices, not coordinates (and the conversion is far from trivial for the outer face).
Dave
CC BY-SA 3.0
2014-11-27T04:35:33.800Z
@NoamZeilberger: you are right, sorry for the confusion. I have the combinatorial embedding *and* a plane drawing (i.e. coordinates) of the graph.
Dave
CC BY-SA 3.0
2014-11-27T08:13:45.697Z
Are your arcs embedded to the plane as straight lines?  If so, then after computing the leftmost vertex, you can compute the arc starting from that vertex whose other end is above this arc but the angle of the arc segment is the leftmost among such arcs.  The face on the left hand side of this arc is the outer face.  If the edges aren't embedded as straight lines, then you need some extra information about the embedding, because in any plane graph 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.
Zsbán Ambrus
CC BY-SA 3.0
2014-11-27T09:19:37.637Z
@ZsbánAmbrus: yes they are. Your method seems to work (need to think about it a little more) and is a little more straightforward than what I have so far. Maybe you could submit it as an answer?
Dave
CC BY-SA 3.0
2014-11-27T19:35:58.207Z
By the way, in cases unlike the OP's where the arcs are not straight (what Noam seems to be arguing about) it should still work to find the leftmost point of the drawing that is either a vertex or an interior point on an arc. The face to the left of that point is the outer face.
David Eppstein
CC BY-SA 3.0
2014-11-28T01:17:16.513Z
@DavidEppstein: I must be missing something, but I really do not see how you detect the "face to the left of that point" in your idea. It is far from a straightforward task...
Dave
CC BY-SA 3.0
2014-11-28T04:56:54.700Z
For the version in which edges are non-straight curves and you use the leftmost point within an arc? If you can find this point, you have some idea what the geometric representation of the arc is that tells you which of its two incident faces is the one to the left. Or you could construct both of the faces it's incident to and compare their areas. For the version with straight edges and leftmost vertex, it's the face between the edges with the greatest and least slopes, the only one whose angle is greater than π.
David Eppstein
CC BY-SA 3.0
2014-11-28T05:04:11.667Z
@DavidEppstein: unfortunately, no. The outer face, such as we have it, is defined as a walk of vertices on the outer boundary. There is no trivial way to tell that such a polygon (which will appear "to the right" of your vertex) is supposed to indicate its *outer* region (which would indeed be "to the left" of the vertex). That is the base of all problems here.
Dave
CC BY-SA 3.0
2014-11-28T06:08:17.627Z
Well I must be misunderstanding something basic because this still looks completely trivial to me and all your and Noam's yelling at me that I have it wrong is failing to convince. Leftmost vertex: easy to find. Angle greater than π among the angles between adjacent edges at that vertex: easy to find. Face walk that includes that angle: easy to find. The fact that you need to interpret the face that you get from this walk as being outside the polygon formed by the walk rather than inside: irrelevant to completing all of these steps.
David Eppstein
CC BY-SA 3.0
2014-11-28T06:13:59.937Z
@DavidEppstein: I am sorry if I gave off any impression of berating you: I appreciate any effort to answer and think this over. However, I think you are indeed missing some important aspect (and/or I failed to convey it properly). As I wrote above, faces are defined as arc/vertex walks. The only thing making the outer face different is its direction. Given an arbitrary point in the outer face (e.g. left of the leftmost vertex) and the outer face (as defined by its vertices), it is *still* not possible to (easily) tell whether the point belongs to the face.
Dave
CC BY-SA 3.0
2014-11-28T06:33:10.533Z
Which of the three steps of my previous comment (finding leftmost vertex, finding big angle, finding face walk that includes that angle) involves testing whether some arbitrary point is inside or outside a polygon? And if you do want to test this, once you've done the face walk part, use a standard point-in-polygon test and invert the sign.
David Eppstein
CC BY-SA 3.0
2014-11-28T06:39:48.480Z
@DavidEppstein: I was addressing your original suggestion of simply "finding the face left of the vertex". The solution  you describe now is essentially a (slightly more complex) version of what Zsban suggested, which I agree should work very nicely.
Dave
CC BY-SA 3.0
2014-11-28T07:12:15.697Z
That was the solution I had in mind all along. I was assuming you could work out the details of using through the combinatorial embedding to find that face from the vertex rather than getting hung up on questions of points outside the drawing and which face they belong to. That (my assumption that you could work out the details) was why I initially stated this as a terse comment rather than giving you a more detailed answer.
David Eppstein
CC BY-SA 3.0
2014-11-28T07:15:49.150Z
My (very peripheral) comment about figuring whether a point belonged to the outer face was just an illustration of why the problem was not trivial. As for the rest, I am sorry, but except for the idea of using the leftmost point, your initial comment was essentially a tautology: "to find the outer face, just use a simple method to find the outer face"... Had I have such a method to start with, I probably would not have asked here. Thanks for your help anyway.
Dave
CC BY-SA 3.0
2014-12-02T04:31:30.883Z
If you think that an answer telling you (1) a vertex that is on the face you want, and (2) where in the embedding around that vertex to look for the face you want is somehow tautological and uninformative, then I think that this site is not for you. Maybe you should try a lower-level CS Q/A site rather than one that expects research-level questions and answers.
David Eppstein
CC BY-SA 3.0
2014-12-02T10:57:50.983Z
@DavidEppstein: there is absolutely no (2) in your initial comment ("left of the vertex" is not a trivial task). By the time I was able to get those details from you, the accepted answer had already been posted. Your comment was definitely a crucial step in the right direction, but far from a full answer, "lower-lever" or not, which is the point of such a site.
Dave
CC BY-SA 3.0
2014-12-02T18:29:36.983Z
My assertion is that "left of a vertex" is indeed a trivial task, and can be accomplished by looking at the angles formed by the incident faces at that vertex (between each pair of incident vertices) to see which one is the left one. As you should have known 30 comments ago if only you were willing to think a little bit instead of demanding that everything be spoon-fed to you and loudly insisting that anything not completely spelled out is a non-answer.
David Eppstein
CC BY-SA 3.0
2017-07-30T05:01:35.527Z
@Dave: while the issue sort-of-becomes clear upon carefully reading the discussion: if you still care about this question (I, for one, do, having had a similar problem, when trying to do a formal proof of a statement about plane *digraphs*): please not only make it clear that you have coordinates *of some sort*, but *whether, and if so, **what kind** of, coordinates you have for the **edges***. This does not go without saying, since usually people assume (at least for planar graphs without any loops or multiple edges) that the vertex coordinates *determine* the (imagined-as-straight) edges...
Peter Heinig
CC BY-SA 3.0
2017-07-30T05:06:31.640Z
edges...while Noam Zeilberger's very relevant cautionary example above involves a plane multigraph having exactly one vertex and exactly one loop, drawn, usually-smoothly-roundishly, **to the left of the vertex**. This plane graph has precisely two faces. Would you please, as some sort minimal-working-example, **clarify how you, in the situation which made you ask this question, represent this particular one-loop graph**?
Peter Heinig
<graph-theory><graph-algorithms><planar-graphs>
Finding outer face in plane graph (embedded planar graph)
Dave
# Finding outer face in plane graph (embedded planar graph)

(Asked by: username_0 on 2014-11-26)

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!

**Tags:** graph-theory, graph-algorithms, planar-graphs

> **Comments:**
> **username_1**: Is there a reason you can't just look at the face to the left of the leftmost vertex?  
> **username_2**: @DavidEppstein maybe I misunderstand what you mean but I don't think "face to the left of the leftmost vertex" is well-defined: a face can be to the left of an oriented edge, not a vertex.  
> **username_2**: @username_0 by "combinatorial embedding" do you mean combinatorial map (https://en.wikipedia.org/wiki/Combinatorial_map)?  Then no, you cannot determine the outer face just from that data, since a planar combinatorial map can be embedded in different ways on the plane so that any face becomes the outer face.  
> **username_2**: In general it makes sense to talk about the outer face (or "root face") of a *rooted* combinatorial map, that is, a combinatorial map with a distinguished dart chosen as the "root dart".  Then the outer face is usually defined as the face to the right of that dart.  
> **username_1**: He says he has coordinates in the plane. So the leftmost vertex is well defined (the one with the smallest x coordinate) and the face to its left is well defined (the one that you move into if you reduce the x coordinate value even more).  
> **username_2**: @DavidEppstein I think you might be making additional assumptions which aren't in the usual definition of "embedded plane graph"/"plane map" (e.g., in general the graph can contain loops and multiple edges). Have a look at the two planar maps in the middle of page 2 of http://www.labri.fr/perso/zvonkin/Research/belyi.pdf. Does your criterion correctly identify the outer face?  
> **username_1**: I am perfectly aware of the definition of a combinatorial map, but unlike you I am also reading the first sentence of the question, which says "and coordinates in the plane". If we have these coordinates, why not use them?  
> **username_2**: what I'm saying is that identifying the leftmost vertex does not let one determine the outer face, and that the two maps on p.2 of the article I linked to above are both counterexamples to your suggested algorithm. The map on the left has two faces incident to the leftmost vertex and no criterion as far as I can tell (regardless of knowledge of vertex coordinates) for determining which face is "to the left".  The map on the right has only one face incident to the leftmost vertex, but it is actually *not* the outer face.  
> **username_0**: @DavidEppstein: I do have coordinates, which means I can indeed find the leftmost vertex very easily, but I cannot see any method which would give me the *face* left of that vertex in any trivial (or even easy) way. The faces I have are defined as walks of vertices, not coordinates (and the conversion is far from trivial for the outer face).  
> **username_0**: @NoamZeilberger: you are right, sorry for the confusion. I have the combinatorial embedding *and* a plane drawing (i.e. coordinates) of the graph.  
> **username_3**: Are your arcs embedded to the plane as straight lines?  If so, then after computing the leftmost vertex, you can compute the arc starting from that vertex whose other end is above this arc but the angle of the arc segment is the leftmost among such arcs.  The face on the left hand side of this arc is the outer face.  If the edges aren't embedded as straight lines, then you need some extra information about the embedding, because in any plane graph 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.  
> **username_0**: @ZsbánAmbrus: yes they are. Your method seems to work (need to think about it a little more) and is a little more straightforward than what I have so far. Maybe you could submit it as an answer?  
> **username_1**: By the way, in cases unlike the OP's where the arcs are not straight (what Noam seems to be arguing about) it should still work to find the leftmost point of the drawing that is either a vertex or an interior point on an arc. The face to the left of that point is the outer face.  
> **username_0**: @DavidEppstein: I must be missing something, but I really do not see how you detect the "face to the left of that point" in your idea. It is far from a straightforward task...  
> **username_1**: For the version in which edges are non-straight curves and you use the leftmost point within an arc? If you can find this point, you have some idea what the geometric representation of the arc is that tells you which of its two incident faces is the one to the left. Or you could construct both of the faces it's incident to and compare their areas. For the version with straight edges and leftmost vertex, it's the face between the edges with the greatest and least slopes, the only one whose angle is greater than π.  
> **username_0**: @DavidEppstein: unfortunately, no. The outer face, such as we have it, is defined as a walk of vertices on the outer boundary. There is no trivial way to tell that such a polygon (which will appear "to the right" of your vertex) is supposed to indicate its *outer* region (which would indeed be "to the left" of the vertex). That is the base of all problems here.  
> **username_1**: Well I must be misunderstanding something basic because this still looks completely trivial to me and all your and Noam's yelling at me that I have it wrong is failing to convince. Leftmost vertex: easy to find. Angle greater than π among the angles between adjacent edges at that vertex: easy to find. Face walk that includes that angle: easy to find. The fact that you need to interpret the face that you get from this walk as being outside the polygon formed by the walk rather than inside: irrelevant to completing all of these steps.  
> **username_0**: @DavidEppstein: I am sorry if I gave off any impression of berating you: I appreciate any effort to answer and think this over. However, I think you are indeed missing some important aspect (and/or I failed to convey it properly). As I wrote above, faces are defined as arc/vertex walks. The only thing making the outer face different is its direction. Given an arbitrary point in the outer face (e.g. left of the leftmost vertex) and the outer face (as defined by its vertices), it is *still* not possible to (easily) tell whether the point belongs to the face.  
> **username_1**: Which of the three steps of my previous comment (finding leftmost vertex, finding big angle, finding face walk that includes that angle) involves testing whether some arbitrary point is inside or outside a polygon? And if you do want to test this, once you've done the face walk part, use a standard point-in-polygon test and invert the sign.  
> **username_0**: @DavidEppstein: I was addressing your original suggestion of simply "finding the face left of the vertex". The solution  you describe now is essentially a (slightly more complex) version of what Zsban suggested, which I agree should work very nicely.  
> **username_1**: That was the solution I had in mind all along. I was assuming you could work out the details of using through the combinatorial embedding to find that face from the vertex rather than getting hung up on questions of points outside the drawing and which face they belong to. That (my assumption that you could work out the details) was why I initially stated this as a terse comment rather than giving you a more detailed answer.  
> **username_0**: My (very peripheral) comment about figuring whether a point belonged to the outer face was just an illustration of why the problem was not trivial. As for the rest, I am sorry, but except for the idea of using the leftmost point, your initial comment was essentially a tautology: "to find the outer face, just use a simple method to find the outer face"... Had I have such a method to start with, I probably would not have asked here. Thanks for your help anyway.  
> **username_1**: If you think that an answer telling you (1) a vertex that is on the face you want, and (2) where in the embedding around that vertex to look for the face you want is somehow tautological and uninformative, then I think that this site is not for you. Maybe you should try a lower-level CS Q/A site rather than one that expects research-level questions and answers.  
> **username_0**: @DavidEppstein: there is absolutely no (2) in your initial comment ("left of the vertex" is not a trivial task). By the time I was able to get those details from you, the accepted answer had already been posted. Your comment was definitely a crucial step in the right direction, but far from a full answer, "lower-lever" or not, which is the point of such a site.  
> **username_1**: My assertion is that "left of a vertex" is indeed a trivial task, and can be accomplished by looking at the angles formed by the incident faces at that vertex (between each pair of incident vertices) to see which one is the left one. As you should have known 30 comments ago if only you were willing to think a little bit instead of demanding that everything be spoon-fed to you and loudly insisting that anything not completely spelled out is a non-answer.  
> **username_4**: @username_0: while the issue sort-of-becomes clear upon carefully reading the discussion: if you still care about this question (I, for one, do, having had a similar problem, when trying to do a formal proof of a statement about plane *digraphs*): please not only make it clear that you have coordinates *of some sort*, but *whether, and if so, **what kind** of, coordinates you have for the **edges***. This does not go without saying, since usually people assume (at least for planar graphs without any loops or multiple edges) that the vertex coordinates *determine* the (imagined-as-straight) edges...  
> **username_4**: edges...while username_2's very relevant cautionary example above involves a plane multigraph having exactly one vertex and exactly one loop, drawn, usually-smoothly-roundishly, **to the left of the vertex**. This plane graph has precisely two faces. Would you please, as some sort minimal-working-example, **clarify how you, in the situation which made you ask this question, represent this particular one-loop graph**?  

---

## 5 answers

### Answer by username_3 on 2014-11-27. Score: 5 | Accepted answer

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 username_1 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.

> **Comments:**
> **username_0**: This is definitely a huge improvement over my idea (somehow did not occur to me to simply go *up*, as well as left, and be done with it).  One small comment: I am not sure I see what the problem could be with taking the target vertex (connected to $v_1$) that is 1. above (non strictly) $v_1$ and 2. left (non strictly) of $v_1$. Not dealing with angles would make the whole thing a lot easier. Not sure what you mean by an "isolated" vertex... Do you have a specific counter-example in mind?  
> **username_0**: Never mind my previous comment, I think I see what you meant by "isolated vertex" and how it would pose a problem (the case where the leftmost is also the uppermost?)... But at any rate, perhaps the phrase "leftmost angle arc" needs a better definition: it seems to me that it should be the arc with the largest (direct) angle from vector [0, -1] (vertical, below the vertex). Does that seem correct to you?  
> **username_3**: I changed the description of the angle thing, the previous description was too complicated.  
> **username_5**: Replaced "angle closest to vertical" with "maximum slope". Angles are evil (and numerically unstable).  

---

### Answer by username_6 on 2020-03-30. Score: 3

It appears to me that the best way to determine the unbounded face is to compute the signed area of each face. All faces have one sign, and the unbounded face has the opposite sign. You can use the formula for the area of a polygon, given its vertices, from
https://www.seas.upenn.edu/~sys502/extra_materials/Polygon%20Area%20and%20Centroid.pdf
or, use the Java example below.
public static double area(Point[] Vertex)
{
    int i, j, n = Vertex.length;
    double area = 0;

    for (i = 0; i < n; i++)
    {
        j = (i + 1) % n;
        area += Vertex[i].getX() * Vertex[j].getY();
        area -= Vertex[j].getX() * Vertex[i].getY();
    }

    area /= 2.0;

    return (area);
}


---

### Answer by username_7 on 2014-11-26. Score: 3

As you are computing a list of all faces of the graph as a list of oriented walks along their arcs (as you've written) you could compute the area of the face (polygon) efficiently as is suggested in the second algorithm here (since you have plane coordinates of the vertices): [Area of polygon](https://stackoverflow.com/questions/451426/how-do-i-calculate-the-surface-area-of-a-2d-polygon/717367#717367). The face with largest area should be the outer face of your graph.

About using information only in the combinatorial map, I think username_2 is right about that they can be embedded in different ways on the plane. More information about this may be here: [Polynomial Algorithms for Subisomorphism of nD Open Combinatorial Maps](http://liris.cnrs.fr/Documents/Liris-5009.pdf)

> **Comments:**
> **username_0**: This would indeed work, but rather cumbersome (and potentially quite time-consuming, even if it remains O(n))... However, this inspired me toward a working solution that required a lot less effort, so thanks for pitching in!  

---

### Answer by username_8 on 2014-11-27. Score: 0

A non-trivial method can be to calculate the convex hull of the vertices.
(This can only be used if the planar graph generated has a convex outer face, which is most likely the case for most of the graph drawing softwares.)

It seems to be an overkill though but it will give you the face exactly in form of a sequence of vertices given the coordinates of the vertices.
It takes $O(n\log n)$ time to find it. You can use the standard LEDA library to find it easily using its
[subroutine](http://www.algorithmic-solutions.info/leda_guide/geo_algs/convex_hull.html).

However it can also be performed in linear time. Please refer to [this](https://stackoverflow.com/questions/14735164/convex-hull-in-on-time).

> **Comments:**
> **username_0**: Yes, convex hull was my go-to solution. The problem is that in addition to having non-linear complexity (which would worsen the overall complexity of what I am trying to do), it depends on the "niceness" of the graph drawing algorithm: a plane graph could perfectly have concave angles on its outer boundary. Inspired by some other contributions, I have figured a solution that is a bit more straightforward (and definitely O(n)). I will post it and maybe someone can improve it or critique it.  

---

### Answer by username_0 on 2014-11-27. Score: 0

**Edit:** actually, step 2 is wrong (see comments). Anyway, the accepted answer solves this much more elegantly.

Since there does not seem to be any (straightforward/simple) answer so far, I thought I would post what I came up with, with inspiration taken from @DavidEppstein's comment and @username_7's answer:

Figuring out the leftmost/rightmost point indeed seems to be a good start. However, from there, @DavidEppstein's idea is unfortunately not applicable (there is no straightforward way to know the face "left of a vertex" in the plane). Instead this is what I do:

1. Find rightmost point $v\_1$ of graph in the plane.
2. Find rightmost point $v\_2$ connected to $v\_1$.
3. Take the two faces bordering edge [$v\_1$,$v\_2$]. Let the longer one (in number of vertices) be $F\_a$ and the other one $F\_b$.
4. Pick an arc $A\_a$ in $F\_a$ that is not in $F\_b$ (we know there is such an arc since the two faces cannot be identical and $F\_a$ is longer than $F\_b$).
5. If the middle of $A\_a$ is inside the polygon formed by the vertices of $F\_b$ in the plane, $F\_b$ is the outer face, otherwise $F\_a$ is.

I welcome any comment and improvement to the method!

> **Comments:**
> **username_3**: I think this won't work as is, because v_2 may be a vertex not on the outer face.  It can be fixed to work though.  
> **username_0**: Are you certain? We know that $v_1$ is on the outer face. Therefore if $v_2$ is not, it would be inside the outer face and there would be a vertex connected to $v_1$ that is more to the right than $v_2$...  
> **username_5**: (Sorry, let me try again.) No, this doesn't work; the righmost neighbor of the righmost vertex can be in the interior. Imagine a tiny tiny horizontal edge to the left of the rightmost vertex.  
> **username_0**: @JɛﬀE: thanks for the clarification: you mean e.g. a horizontal edge left of $v_1$ while the real outer edges go farther left (the 'tiny tiny' part kind of threw me off). Indeed, that's a problem. I guess there is no way around looking at angles/slope in the way Zsban suggested.  

---

