Find border (boundary) edges of planar graph (geometric shape)

Question

I have vertices and an edge list that describe a planar geometric shape (faces are triangles). For example:

   a_______b
   /|\    /
  / | \  /
e/__|__\/c
    d

Verts: a, b, c, d, e
Edges: (a,b), (a,c), (a,d), (a,e), (b,c), (c,d), (d,e)

So that is all the information I would have about that particular planar geometric shape. In this example, the only internal edges are (a,c) and (a,d). All other edges are border edges. How can I identify those border edges algorithmically (or conversely identify all internal edges)?

Motivation: If it helps, I'm trying to build a navigation mesh, one of the steps of which is to build a visibility graph, the first step of which I think is to identify the border edges.

Answer 1

For planar graphs, the "outer face" property is not unique; you can draw the graph so that any of the faces becomes the outer one, or you can even draw the graph such that it has different faces - consider your example graph:

That said, if you know that the graph can be drawn such that all internal faces are triangular, you could scan the list of edges and check how many triangles they belong to (by checking the neighboring edges). If the edge only belongs to one triangle, it's an outer edge.

Anyway, it seems weird to me, that you would know the graph has such property and not know what the respective planar embedding was at the same moment.

Answer 2

I know is a little bit late. In the F.E.M. community, we count the edges for each triangle then the boundary are the edges that appears once. If it's done with sparse matrices it's pretty fast (to me).