boost - 使用 BOOST 检查图形的外平面性？

Question

我只是在概念上想知道如何检查图形是否是外平面的。我知道您可以使用 BOOST 检查图形中的平面性，如何检查外平面性？提示？

Answer 1

回答可能有点太晚了，但我希望这仍然可以帮助您或其他任何偶然发现这个问题的人。

直到今天，Boost 仍然没有实现任何外平面性测试算法，但使用 Boost 的平面性检查来检查外平面性实际上非常简单。

根据 Manfred Wiegers在线性时间文章中识别外平面图：

如果K ₁ + G（一个新顶点与G的所有顶点相连）是平面的，则图G是外平面的。

因此，您需要向图形添加一个额外的顶点，边将其连接到原始图形的所有顶点，然后检查新图形是否是平面的。如果是这样，那么原始图是外平面的。

另请注意，每个具有 n 个顶点的外平面图的边数少于 2n-3。添加这个边数检查可以快速过滤掉许多明显的非外平面图。