Find the outer edges of a graph

Question

What is the best way to find the outer edges of a graph?

For example, the red edges on this graph:

I don't know if this algortithm has a name. The name it would be enough to help me find something on Google.

Answer 1

I hope I haven't misunderstood the question but I don't think there's an answer unless you have a specific plane embedding for the graph.

Even for most planar graphs¹, you can rearrange the nodes so that different edges are on the "outside". See Find border (boundary) edges of planar graph (geometric shape). Your example is decidedly not planar.

If you have an embedding, what you're looking for is related to the convex hull of a set of points. Here's a Dr. Dobb's article about it http://www.drdobbs.com/architecture-and-design/building-the-convex-hull/201806315. The "gift-wrapping" algorithm is simple to implement.

However, the boundary of a given graph embedding may not be convex so you would have to modify to the algorithm to recalculate portions of the convex hull that are not edges. (You could call it the "shrink-wrapping" algorithm).

note 1: The only class of graphs I can think of that have unique embeddings in the plane are cycle graphs. There could easily be others. (edit: unique with respect to boundary at least, you can embed a cycle clockwise or counterclockwise)

Answer 2

A graph is simply a set of vertices and a set of edges. There is no notion of "outer edges" inherent to a graph. For example, in the graph you gave as an example, the edges forming a pentagon could be moved inside.