algorithm - 如何证明平面嵌入？

Question

我将要实现一个计算平面嵌入的算法。

我已经开始通过运行一组图表 (rome graphs) 并将我的结果与另一个实现 (yfiles) 的结果进行比较来验证我的结果。但是，我只能检查平面/非平面答案是否相等，因为对于给定的平面图，可能存在许多不同的嵌入。

如何验证我计算的嵌入(在邻接列表中排序)是正确的平面嵌入？

我已经发现了一些可能嵌入错误的情况。对于失败的图表，通常手动绘制嵌入会变得很困难。我发现 boost docs说明给定任意一个图，可以画出一个图的平面图，证明该图是平面的，平面性证明容易检验。但我也不确定我是否/如何能够仅从有序的邻接列表中以一种万无一失的算法方式创建这样的绘图。

(顺便说一下，这是我的 code )

Answer 1

据我所知，最简单的方法是计算任意生成树，然后验证对偶图中剩余的边没有环。如果dnext(e)将一个头部为v的半边e按逆时针顺序映射到下一个头部为v的半边，sym(e)为与e相反的半边，则rprev(e) = sym(dnext (e)) 是下一个具有相同右面的顺时针半边。我在我的一个项目的 Algorithm.java 中实现了这种方法:http://www.davideisenstat.com/trickle/

或者，您可以使用欧拉特征。标记顶点(= 排列 dnext 的循环)和面(= 排列 rprev 的循环)并确定存在多少连通分量。验证 (V - C) + (F - C) = E。