查找图形的外边缘

我希望我没有误解这个问题,但我认为除非你为图嵌入了一个特定的平面,否则没有答案。

即使对于大多数平面图 ^1. ,可以重新排列节点,使不同的边位于“外侧”。看见 Find border (boundary) edges of planar graph (geometric shape) 你的例子显然不是平面的。

如果你有一个嵌入,你要寻找的是与 凸包 一组点的。这是多布医生的一篇文章 http://www.drdobbs.com/architecture-and-design/building-the-convex-hull/201806315 。“礼品包装”算法实现起来很简单。

然而,给定图嵌入的边界可能不是凸的,因此您必须修改算法以重新计算凸包中不是边的部分。(你可以称之为“收缩包装”算法)。

注释1 :我能想到的唯一一类在平面中具有唯一嵌入的图是循环图。很容易就会有其他人。(编辑:至少相对于边界是唯一的,您可以顺时针或逆时针嵌入循环)

图只是一组顶点和一组边。图中不存在固有的“外边缘”概念。例如,在你举的例子中,形成五边形的边可以向内移动。