找到圖的外邊緣

Question

找到圖的外邊緣的最佳方法是什麼？

例如，在此圖中的紅色邊緣：

我不知道這是否algortithm有一個名字。這個名字足以幫助我在Google上找到一些東西。

Answer 1

我希望我沒有誤解這個問題，但我不認爲有一個答案，除非你有一個特定的平面嵌入圖。

即使對於大多數平面圖形，您可以重新排列節點，使不同的邊緣位於「外部」。見Find border (boundary) edges of planar graph (geometric shape)。你的例子絕對不是平面的。

如果你有一個嵌入，你要找的是與凸包有關的一組點。這是Dobb博士的文章http://www.drdobbs.com/architecture-and-design/building-the-convex-hull/201806315。 「禮品包裝」算法很容易實現。

但是，給定圖形嵌入的邊界可能不是凸的，所以您必須修改算法以重新計算凸邊不是邊的部分。 （你可以稱它爲「收縮包裝」算法）。

note1：我能想到的唯一一類圖表在平面中具有獨特的嵌入是循環圖。其他人可能很容易。 （編輯：至少關於邊界是唯一的，你可以順時針或逆時針嵌入一個循環）

Answer 2

圖形只是一組頂點和一組邊。沒有圖形固有的「外邊緣」的概念。例如，在您給出的圖表中，作爲五邊形的邊緣可以在內部移動。