我即将实现一种计算平面嵌入的算法。
我已经开始通过运行一组图（罗马图）并将我的结果与另一个实现的结果（yfiles）进行比较来验证我的结果。但是，我只能检查平面/非平面答案是否相等，因为对于给定的平面图，可能存在许多不同的嵌入。
如何验证我计算的嵌入（在邻接列表中排序）是正确的平面嵌入？
我已经发现了一些我可能得到错误嵌入的情况。对于失败的图，通常手动绘制嵌入变得很困难。我发现boost 文档指出，给定任何图形，都可以生成图形的平面图，这将证明该图形是平面的，并且平面性证书很容易检查。但我也不确定是否/如何仅从有序的邻接列表中以一种万无一失的算法方式创建这样的绘图。
（顺便说一句。这是我的代码）
我知道的最简单的方法是计算任意生成树，然后验证剩余边在对偶图中没有循环。如果 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。