图的平面性检测算法

图的平面性检测是判断一个给定图是否能被画在平面上使得边不相交的重要问题。我将从基本概念开始，逐步介绍经典的平面性检测算法。

1. 平面图回顾与检测必要性

   • 平面图是指可以嵌入在二维平面上且边之间除端点外不相交的图。虽然平面图的定义直观，但直接判断任意图的平面性十分困难。
   • 例如，完全图K5和完全二分图K3,3是非平面图的典型代表（Kuratowski定理指出，任何非平面图都包含K5或K3,3的细分）。
   • 平面性检测算法的目标是高效地判断一个图是否为平面图，如果是，则可能输出一个平面嵌入（边的排列方式）。

2. 早期算法与Kuratowski定理应用

   • 基于Kuratowski定理的朴素方法是搜索图中是否包含K5或K3,3的细分，但这种搜索是指数级复杂的，不适用于大规模图。
   • 20世纪60年代，研究者提出了更高效的算法，如基于“逐边添加”的思路：逐步将图的边添加到平面中，检查是否会导致交叉。

3. DMP平面性检测算法（1964）

   • Demoucron、Malgrange和Pertuiset提出的算法是第一个多项式时间算法，核心思想是“片”的概念。
   • 步骤：
     a. 从图的一个环开始，将其嵌入平面。
     b. 对于剩余部分，找出所有“片”（即不能通过当前嵌入部分分割的连通分支）。
     c. 检查每个片是否能嵌入到当前面的内部而不冲突。如果某个片只能嵌入到同一个面，则尝试扩展嵌入；如果多个片要求同一个面且无法共存，则图非平面。
   • 该算法复杂度为O(n²)，奠定了后续算法的基础。

4. Hopcroft-Tarjan算法（1974）

   • 这是一个线性时间O(n)算法，利用了深度优先搜索（DFS）和平面图的特定结构。
   • 关键步骤：
     a. 通过DFS生成一棵生成树，并记录顶点的DFS编号和低点值（lowpoint）。
     b. 基于DFS路径将图分解为“路径添加”序列，确保在添加边时能快速检查平面性条件。
     c. 使用栈结构管理边的嵌入顺序，避免回溯。
   • 该算法是第一个最优线性算法，但实现复杂，侧重于理论突破。

5. 基于左-right规划的统一方法

   • 后续算法如Boyer-Myrvold（2004）改进了实用效率，结合了DFS和“嵌入扩展”策略。
   • 核心思想：在DFS过程中，维护一个可能嵌入的集合，通过旋转和调整局部嵌入来避免冲突。
   • 这种方法能在O(n)时间内处理大规模图，并被用于实际软件实现。

6. 应用与扩展

   • 平面性检测算法是图绘制、电路板设计等领域的基础工具。
   • 扩展问题包括：输出所有平面嵌入、处理有向图或加权图的平面性，以及近似算法用于近平面图。

通过这些步骤，平面性检测从理论判定发展为高效实用算法，体现了图论中组合结构与计算方法的深刻联系。