C# 中的平面嵌入（平面遍历）算法

Question

我有一个图G。该图是平面图。

我希望找到图表的所有面。我明白 构建平面嵌入是查找面（或区域或循环）的方法，使得所有边必须由最多 2 个面共享。

C# 中是否有易于实现的平面嵌入算法？商业或开源都可以。

Answer 1

在这里，这个 C# 项目表示它受到 Boost 库的启发，并表示它支持：

• 检查给定的无向图是否是平面的
• 如果给定的图是平面的，则计算平面嵌入
• ​​计算给定平面嵌入的面

它似乎使用 Boyer -Myrvold 平面性测试：

• 检查图是否是一个大循环，是否是平面的，并且嵌入中恰好有两个面
• 检查是否随机图具有超过 3n - 6 个顶点，是否不是平面

https://github.com/OndrejNepozitek/GraphPlanarityTesting

Answer 2

经过一番搜索，我发现平面面遍历 Boost库中的函数满足我的需求。

然后，可以用纯 C 方式包装该函数，并通过 PInvoke 从 C# 调用它。