是否有确定平面图面的算法？

Question

我正在开发一个 Java 程序，以各种方式分析图形，特别是具有加权边的无向图。我现在试图，给定一个平面图，确定它的面，也就是由图的边缘分隔的“空间”的封闭区域，但我真的找不到一种算法，或者至少是一个可以理解的算法，可以做到这一点我正在努力实施我的其中之一。

有人有什么想法吗？

PS：我应该注意，我没有扎实的图论基础知识

Answer 1

平面图的面取决于将平面图嵌入到表面上。出现的问题是平面图可能有多个嵌入。

例如：

   ----1----         ----1----      
  /   / \   \       /   / \   \     
 /   /   \   \     /   /   \   \    
2   3-----4   |   2   4-----3   |   
 \   \   /   /     \   \   /   /    
  \   \ /   /       \   \ /   /     
   ----5----         ----5----      

上图可以以两种不同的方式嵌入，每种方式都有不同的面。

所以第一个问题是生成任何单个嵌入；最有效的平面度测试将通过生成嵌入来测试平面度（而不是使用效率较低的方法，例如寻找禁止的未成年人），因此您应该能够为此使用任何平面度测试。更难的问题是生成所有可能的嵌入 - 然而，在通过路径添加进行平面测试中有一个解决方案（并在附录中包含 Java 代码来执行平面测试、生成嵌入、从双连通图的一个嵌入循环到其他嵌入并为嵌入的每个顶点生成循环边阶）。

一旦有了嵌入，就可以将图表示为每个顶点的循环边阶。因此，对于左侧示例：

Vertex Clockwise Edge-Order
------ --------------------
     1              2,5,4,3
     2                  1,5
     3                1,4,5
     4                1,5,3
     5              1,2,3,4

然后要找到这些面，您只需从一条边开始，顺时针或逆时针选择，然后继续从连续顶点沿该方向选择下一个相邻边，直到返回起始边：

Clockwise (2,1) -> (1,5) -> (5,2)
Clockwise (1,2) -> (2,5) -> (5,3) -> (3,1)
Clockwise (1,3) -> (3,4) -> (4,1)
Clockwise (1,4) -> (4,5) -> (5,1)
Clockwise (4,3) -> (3,5) -> (5,4)

并且您拥有面（并且每个边缘都被访问了两次 - 每个方向一次）。