如何从平面图的边列表或邻接列表表示到面列表？
例如，对于这张图(奇怪的是，它不是从 0 开始索引的):
我想要一个看起来像这样的列表:
[
[1,2,8,7],
[1,2,4,3],
[1,3,5,7],
[2,4,6,8],
[5,6,7,8],
[3,4,6],
[3,5,6]
]
它不必采用那种格式或顺序，但它应该是某种包含所有面孔的列表(或集合)。包括外表面。
对于具有 V 个顶点的图(E=O(V)，因为是平面的)，算法应在 O(V) 中生成此列表。
最佳答案
您需要生成图形的平面嵌入。一个问题是双连通图通常可以生成多个平面嵌入。
"Planarity Testing by Path Addition" PhD thesis 中给出了一种平面性测试和嵌入算法这解决了生成图的所有可能平面嵌入的问题(在 O(V+E) 时间和内存中，对于具有 V 个顶点和 E 个边的双连通图的单个嵌入，以及 O(P(V+E) ) 时间和 O(V+E) 内存来生成所有可能的唯一平面嵌入，其中 P 是嵌入的排列数)。
第 5 章详细介绍了测试图的平面性所需的算法，然后为每个顶点生成循环边顺序(以及如何迭代到嵌入的下一个排列)。
给定循环边顺序，您可以通过获取每条边并在到达每个连续顶点时遵循循环边顺序中的下一个顺时针(或逆时针)边来生成图形的面。
关于algorithm - 面的邻接或边列表，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/43882782/