algorithm - 平面度测试算法实现

Question

我想编写一个算法，将图形作为输入，如果它是平面则返回 true，否则返回 false。我四处搜索，发现了大量的算法，但没有容易理解的实现。

有没有像 Boyer-Myrvold's 或 C++ 或 Java 中可用的任何其他实现，可以满足我的要求？

Answer 1

Boyer-Myrvold 的 Boost 中的实现非常容易理解，并且得到了很好的评论。

https://www.boost.org/doc/libs/1_67_0/boost/graph/planar_detail/boyer_myrvold_impl.hpp

不过，如果不先阅读原始论文，我不会尝试阅读代码。

Answer 2

本文对Planarity Testing的Path Addition方法进行了详细的描述（包括数学理论和算法实现）。

完整的 Java 源代码也包含在支持的附录中：

• 平面度测试；
• 生成平面嵌入；和
• 循环生成双连通图的所有可能的平面嵌入（在线性时间内与边数和嵌入数成正比以生成所有嵌入）。