algorithm - 平面嵌入中的最左边路径

Question

我有一个有向平面图。因此我可以进行平面嵌入。我必须节点 s 和 t 并且我想根据特定的嵌入找到 s 和 t 之间最左边的路径。

左定义为评论中描述的大卫。这意味着“左”是相对于无限面和顺时针/逆时针约定定义的。如果循环 p*rev(q) 相对于缠绕无限面而言至少与任何其他面一样逆时针，则路径 p 位于具有相同端点的路径 q 的左侧。

这怎么可能？我不知道如何告诉我的程序是否留下了另一条路径。我读了几篇论文，但他们没有解释如何实现它。有人有想法吗？

Answer 1

一个简单的平面图没有左右的概念，它可以被镜像和旋转，仍然是平面的。您必须在图表中嵌入某种方向。

如果节点的最大出度为 2，则可以标记左边缘。要找到最左边的路径，您可以从 s 开始进行深度优先搜索。当你到达一个新节点时，总是先取左边缘。当达到 t 时，该算法应该终止，让您离开最左边的路径。

在任意最大出度的情况下，您可以用从左到右递增的数字标记边缘。

Answer 2

正如 user3568609 所说，平面嵌入是在一个球体上，左右没有自然定义。你需要先选择一张无限的脸；对于流算法（我假设这是您正在实现的），选择与 s 或 t 相关的面部事件通常很方便。让我们假设无限面与 t 相关。进入 t 的半边的逆时针顺序现在在无限面所在的位置有一个自然间隙。

.4  3| /2  .
 \___|/___/
     t  1

(infinite face)

以逆时针顺序访问半边，在示例中为 1 到 4。这是深度优先遍历，所以我们在 2 之前充分探索 1 的连接，等等。当你从另一个顶点 u 到达另一个顶点 v 时，图片看起来像这样

|3   |2
 \___|___/1
     v
     |
     u

我再次标记了正确的遍历顺序。