Finding outer face in plane graph (embedded planar graph)

Question

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!

Answer 1

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.

Answer 2

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. The face with largest area should be the outer face of your graph.

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: Polynomial Algorithms for Subisomorphism of nD Open Combinatorial Maps

Answer 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 4

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.

However it can also be performed in linear time. Please refer to this.

Answer 5

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 @kudy'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!