如何认证平面嵌入？

Question

我即将实现一种计算平面嵌入的算法.

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

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

我已经发现了一些可能导致嵌入错误的情况.对于失败的图形,通常手动绘制嵌入变得困难.我发现增强文档声明给定任何图形,可以产生图形的平面绘图,这将证明图形是平面的并且平面度证书易于检查.但我也不确定是否/如何以一种傻瓜式的算法方式从有序的邻接列表中创建这样的绘图.

(顺便说一下,这是我的代码)

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。