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 angle is the closest to pointing up. This arc will be a side of the unbounded face. (You must consider the angle, 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.

Update: clarified the second step.

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.

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 and go upwards, find the one whose angle is the closest to pointing left. This arc will be a side of the unbounded face. (You must take the arc with the leftmost angle, 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.

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 angle is the closest to pointing up. This arc will be a side of the unbounded face. (You must consider the angle, 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.

Update: clarified the second step.