【知识总结】 可平面图的判断

可平面图的判断

剖分

• 剖分：在一条边上加入一个新的顶点，将其分为两条边
• Kuratowski子图：图中的，是或剖分的子图
• Kuratowski定理：可平面图的充要条件是没有kuratowski子图
• Wagner定理：可平面图的充要条件是没有可以收缩到或的子图

DMP算法

H-fragment

图的：给定的子图，的是中去掉后剩余的“连通分支”，包括：

• 一条不在中但两个端点都在中的边及其两端
• 的一个连通分支加上它连到H的边及其端点

基本思路

• 迭代地嵌入当前子图的fragment，直到G全部被嵌入（可平面）或者某个fragment无法嵌入（不可平面）
• 嵌入一个fragment可能难以操作，但总能嵌入其中的一条路
• 图是可平面的当且仅当的每个块都是可平面的

DMP算法流程

• 如果有多个块，只需要检测每个块（2-连通图）是否可平面即可
• 对于每个2-连通图，从中任取一个圈，平面嵌入
• 迭代如下
  • 找到所有
  • 对于每个（称作），在中找到所有包含所有的附着点的面（称为）。如果某个为空，则不可平面；如果某个 则选中这个；如果每个，则任选一个
  • 从选中的中任选一条连接两个附着点的路，将嵌入到的一个面中。
  • 将结果记作
  • 如果则可平面，否则继续迭代。

复杂度

• 块分解：，基于DFS
• 找初始的圈：
• 迭代轮数:
  • 简单平面图满足
  • ，因此每轮迭代新增一个面
• 每轮的迭代时间：