图的可平面性与平面图判定 图的可平面性研究的是图能否在平面上绘制，使得任意两条边仅在顶点处相交。这是图论中一个基础而深刻的问题，与图的拓扑结构、算法复杂性紧密相关。 第一步：理解可平面性的基本定义 一个图 \( G = (V, E) \) 被称为 可平面图 ，如果存在一种在平面上的绘制方式，使得它的边仅在端点处相交。这样的绘制称为图的一个 平面嵌入 。平面嵌入将平面划分成若干个连通的区域，这些区域称为 面 。其中，无界的外部区域也是一个面。例如，树和所有顶点数不超过4的完全图都是可平面图，而完全图 \( K_ 5 \) 和完全二分图 \( K_ {3,3} \) 则不是可平面图。 第二步：掌握可平面图的必要条件——欧拉公式 对于一个连通的平面图，设其顶点数为 \( v \)，边数为 \( e \)，面数为 \( f \)，则满足欧拉公式：\( v - e + f = 2 \)。欧拉公式是判断一个图是否可平面的重要工具。利用它可以推导出平面图的一些必要条件，例如，对于 \( v \geq 3 \) 的简单平面图，有 \( e \leq 3v - 6 \)；如果图不包含三角形，则 \( e \leq 2v - 4 \)。若一个图违反这些不等式，则它一定不是可平面图。 第三步：认识可平面性的核心判据——库拉托夫斯基定理与瓦格纳定理 库拉托夫斯基定理指出，一个图是可平面图，当且仅当它不包含同胚于 \( K_ 5 \) 或 \( K_ {3,3} \) 的子图。这里的“同胚”意味着可以通过对边进行细分（在边上插入顶点）得到。瓦格纳定理则给出了另一个等价表述：一个图是可平面图，当且仅当它不包含 \( K_ 5 \) 或 \( K_ {3,3} \) 作为其缩图。这两个定理从结构上刻画了可平面图的特征，是理论判定的基石。 第四步：学习实用的平面性判定算法 尽管库拉托夫斯基定理提供了理论依据，但直接用它来判定大规模图的平面性效率很低。因此，人们开发了高效的平面性判定算法。经典的算法包括： DMP 算法 ：由 Demoucron, Malgrange 和 Pertuiset 提出，是一种基于路径追加的直观算法，通过逐步构建平面嵌入来判定。 Hopcroft-Tarjan 算法 ：这是第一个线性时间 \( O(v) \) 的平面性判定算法，基于深度优先搜索，能够高效地找出图的一个平面嵌入或证明其不可平面。 Boyer-Myrvold 算法 ：一种更现代的线性时间算法，在实际应用中表现出色。 第五步：了解可平面性在其他领域的应用与扩展 图的可平面性概念可以扩展到其他曲面，例如环面（亏格为1的曲面）。一个图如果在环面上可以无交叉地绘制，则称为环面图。更一般地，图的 亏格 定义为图能无交叉地嵌入的最小 orientable 曲面的亏格。此外，可平面性在电路板布线、地理信息系统（GIS）以及图的可视化中都有直接的应用，确保图形显示清晰无重叠。