我只是想了解如何检查图形是否为外平面图。我知道您可以使用BOOST检查图形的平面性，那么如何检查外平面性？提示？
1个回答
2
也许回答有点晚了，但我希望这仍然能帮助到你或其他遇到此问题的人。迄今为止，Boost仍未实现任何外平面性测试算法，但使用Boost的平面性检查可以轻松检查外平面性。
根据Manfred Wiegers的“在线性时间内识别外平面图”文章：
引用： 如果一个图G是外平面图，则K1+G（一个新顶点连接到G中的所有顶点）是平面图。
因此，您需要向图形添加一个附加顶点，并使用边将其连接到原始图形的所有顶点，然后检查新图是否为平面图。 如果是，则原始图形是外平面图。
还要注意，每个具有n个顶点的外平面图都具有少于2n-3条边。 添加此边计数检查可以快速过滤掉许多明显非外平面图。
根据Manfred Wiegers的“在线性时间内识别外平面图”文章：
引用： 如果一个图G是外平面图，则K1+G（一个新顶点连接到G中的所有顶点）是平面图。
因此，您需要向图形添加一个附加顶点，并使用边将其连接到原始图形的所有顶点，然后检查新图是否为平面图。 如果是，则原始图形是外平面图。
还要注意，每个具有n个顶点的外平面图都具有少于2n-3条边。 添加此边计数检查可以快速过滤掉许多明显非外平面图。
- Adrian Ostrowski
1
嗨，欢迎来到stackoverflow。请更详细地描述答案。当你在答案中添加链接时，有可能页面会被删除，而你的答案对其他人来说就变得无用了。 - undefined
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接