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)