OI-wiki 平面图（Planar Graph）完全指南：从欧拉公式、对偶图到平面性判定算法-港品优选

OI-wiki 平面图（Planar Graph）完全指南：从欧拉公式、对偶图到平面性判定算法

【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki

本文是 OI-wiki 图论模块中平面图一文的完整展开。平面图（planar graph）是图论与算法竞赛中一类结构优美、应用广泛的图：从欧拉公式 $|V|-|E|+|F|=2$ 到"平面图最小割化为对偶图最短路"这一经典技巧，再到 Kuratowski / Wagner 禁用图刻画与线性时间的平面性判定算法，本文将系统梳理这些概念、定理及其证明，并结合本仓库图论模块的相关文档（图论基础概念、最小割、最短路等）说明其在解题实战中的落地方式。读完本文，你将能够准确区分"可平面图"与"平面图"、熟练运用欧拉公式推导边数上界、构造平面图的对偶图并完成最小割到最短路的转化，同时了解平面性判定的理论与算法脉络。

平面图的基本概念

如果图 $G$ 能画在平面 $S$ 上，即除顶点处外无边相交，则称 $G$ 可嵌入平面 $S$，$G$ 为可平面图（planar graph）。画出的没有边相交的图称为 $G$ 的平面表示或平面嵌入（planar embedding）。可平面图的这个平面嵌入也称为平面图（plane graph）。

[!info] 「平面图」的术语辨析不同中文文本中，「平面图」的含义可能不同。在本文的定义中，可平面图是一个图论对象，它可能以不同的方式嵌入平面中；平面图则是一个几何对象，除了图论结构外，它还需要指定图的绘制方式。同一个可平面图往往对应着多个平面图。因此，如果结论只依赖于图论结构，就使用「可平面图」一词；如果还依赖于图的平面嵌入方式，就使用「平面图」一词。

以下是平面图的简单例子（左：蝴蝶图；右：$4$ 阶完全图 $K_4$）：

以下是不可平面图的简单例子（左：$5$ 阶完全图 $K_5$；右：两部分各 $3$ 个顶点的完全二分图 $K_{3,3}$）：

在 OI-wiki 的图论基础概念一节中，平面图也被简要定义为"可以画在一个平面上，且没有两条边在非端点处相交"的图，并直接给出了两个重要结论：简单连通平面图满足 $|E|\le 3|V|-6$；以及 Kuratowski 定理。本文将对这两条结论给出完整的推导与证明。

平面图的性质

面及其次数

设 $G$ 是平面图，由 $G$ 的边将 $G$ 所在的平面划分成若干个区域，每个区域称为 $G$ 的一个面（face）。其中，无界的面称为无限面（unbounded face）或外部面（external face），有界的称为有限面或内部面。每一个平面图有且仅有一个外部面。

包围每个面的所有边组成的回路称为该面的边界（boundary），并称边界中的边与该面关联（incident）。边界的长度称为该面的次数（degree）。计算面的次数时，每条割边都算作两次。由此可以得到：

平面图中所有面的次数之和等于边数 $|E|$ 的 $2$ 倍。
平面图中，$1$ 次面的边界对应于图的自环；$2$ 次面的边界通常对应于图的一对重边（但这并非唯一的可能——两个嵌套的自环也会形成二次面；另外，有二次面未必意味着图不是简单的，例如一个只有一条边的图中，唯一的面（即外部面）也是二次的）。
顶点数 $|V|\ge 3$ 的简单连通平面图中，所有面次数都至少为 $3$。

欧拉公式

平面图的一个重要性质是欧拉公式（Euler's formula），它给出了图的顶点数 $|V|$、边数 $|E|$ 和面数 $|F|$ 之间的关系。

[!note] 欧拉公式对于连通的平面图 $G$，有 $$ |V| - |E| + |F| = 2. $$

证明：对面数 $|F|$ 应用数学归纳法。归纳起点是 $|F|=1$。此时平面图有且只有一个外部面，全部边都是割边，所以图 $G$ 是一棵树，必然有 $|E|=|V|-1$，代入欧拉公式即可发现它成立。假设欧拉公式对于面数 $|F|=k$ 的平面图成立。对于面数 $|F|=k+1$ 的平面图 $G$，必然存在非割边 $e$，它是两个不同的面的公共边。将边 $e$ 从图中删除得到图 $G-e$，它有 $|V|$ 个顶点、$|E|-1$ 条边和 $|F|-1$ 个面。由归纳假设，对图 $G-e$ 成立欧拉公式，即 $|V|-(|E|-1)+(|F|-1)=2$，整理即得关于图 $G$ 的欧拉公式。根据数学归纳法，欧拉公式对所有平面图都成立。$\blacksquare$

[!note] 推论（多连通分支情形）对于有 $k$ 个连通分支的平面图 $G$，有 $$ |V| - |E| + |F| = k + 1. $$

证明：图 $G$ 的每个连通分支都是平面图，但这些连通分支共用同一个外部面。直接对这些连通分支应用欧拉公式并累加，总顶点数和总边数都是正确的，但总面数多了 $k-1$，因为唯一的外部面总共计数了 $k$ 次。将这一修正考虑在内，就得到 $|V|-|E|+|F| = 2k - (k-1) = k+1$。$\blacksquare$

由此可以推出平面图的边与顶点的数量关系。

[!note] 定理（面次数下界导出边数上界）对于有 $k$ 个连通分支的平面图 $G$，如果图 $G$ 的每个面次数都至少为 $l \ge 3$，那么有 $$ |E| \le \dfrac{l}{l-2}(|V|-k-1). $$

证明：因为 $G$ 的各面次数至少为 $l$，所以所有面的次数和至少为 $l|F|$，亦即 $2|E| \ge l|F|$。代入欧拉公式的推论 $|V|-|E|+|F|=k+1$，得到 $2|E| \ge l(k+1-|V|+|E|)$。利用 $l\ge 2$ 解出 $|E|$，即得 $|E| \le \dfrac{l}{l-2}(|V|-k-1)$。$\blacksquare$

[!note] 推论（稀疏性）设 $G$ 是简单可平面图，且 $|V|\ge 3$，那么有 $$ |E| \le 3|V|-6. $$

证明：当 $G$ 连通时，所有面次数都至少是 $3$，在上述定理中取 $k=1$ 且 $l=3$，即得 $|E|\le 3|V|-6$。当 $G$ 不连通时分为两种情形：

如果存在连通分支顶点数至少是 $3$，那么对这些连通分支可分别建立 $|E_i|\le 3|V_i|-6$；顶点数小于 $3$ 的连通分支一定有 $|E_i|\le |V_i|\le 3|V_i|$。将所有不等式相加，就得到 $|E|\le 3|V|-6$。
如果所有连通分支顶点数都小于 $3$，那么整体有 $|E|\le |V|$；又因为 $|V|\ge 3$ 时 $|V|\le 3|V|-6$，所以结论仍成立。$\blacksquare$

这一推论说明简单可平面图是稀疏图——这也是很多平面图算法可以做到线性复杂度的结构性原因，后面介绍的线性平面性判定算法正是建立在这一稀疏性之上。

对偶图

平面图都有相应的（几何）对偶图（dual graph），这也是平面图理论中最重要的工具之一。

设 $G$ 是平面图，可以按下述步骤绘制图 $G^*$：

在 $G$ 的每个面 $f_i$ 内部都绘制一个点 $v_i^*$；
对 $G$ 的每条边 $e$，如果 $e$ 在面 $f_i$ 和 $f_j$ 的公共边界上，就绘制一条连接 $v_i^$ 和 $v_j^$ 的边 $e^$，使之与 $e$ 恰相交一次，且不与其他图 $G$ 或图 $G^$ 的边相交。特别地，当 $e$ 只出现在一个面 $f_i$ 的边界上时，需要绘制一条与 $v_i^*$ 关联的自环，使之与 $e$ 相交。

这样得到的图 $G^*$ 就称作图 $G$ 的对偶图。

[!note] 定理设图 $G^$ 是平面图 $G$ 的对偶图。那么图 $G^$ 是连通的平面图。而且，图 $G^{**}$ 与 $G$ 同构，当且仅当 $G$ 是连通图。

证明：图 $G^$ 的平面性由构造过程保证。连通性方面，对图 $G^$ 中任意两个顶点 $v_i^,v_j^$，设平面中连接它们的直线段经过图 $G$ 的面和边依次为 $f_i,e_{s_1},f_{s_1},\cdots,f_{s_{r-1}},e_{s_r},f_j$，它们分别对应对偶图中的顶点和边 $v_i^,e_{s_1}^,v_{s_1}^,\cdots,v_{s_{r-1}}^,e_{s_r}^,v_j^$。由构造可知，序列中相邻的顶点和边是相关联的，因此这描述了图 $G^$ 中的一条途径，所以 $G^$ 连通。

由于 $G^{}$ 是 $G^*$ 的对偶图，必然连通，所以 $G$ 与 $G^{}$ 同构的必要条件是 $G$ 连通。为证明充分性，只需证明当 $G$ 连通时，$G$ 满足 $G^$ 的对偶图的构造要求。因为 $G^$ 的边与 $G$ 的边天然对应，只需证明 $G^$ 的每一个面都恰好包含 $G$ 的一个顶点。对 $G^$ 的任一个面 $f^$，设 $e^$ 是其边界上的一条边，那么 $G$ 中对应的边 $e$ 的端点之一必然在面 $f^$ 之内，故面 $f^$ 中至少存在 $G$ 的一个顶点。由于 $G^$ 和 $G$ 都连通，欧拉公式成立；而 $G$ 与 $G^$ 边数相同、$G$ 的面数等于 $G^$ 的顶点数，所以 $G$ 的顶点数等于 $G^$ 的面数。于是 $G^*$ 的每个面恰好只有 $G$ 的一个顶点。$\blacksquare$

平面图与其对偶图的结构之间有很多对应关系，这些对应关系是"对偶化"解题思路的理论基础：

$G$ 中的面对应 $G^$ 中的点，$G$ 中的边对应 $G^$ 中的边，$G$ 中的点对应 $G^*$ 中的面；
$G$ 中的自环对应 $G^$ 中的割边，$G^$ 中的自环对应 $G$ 中的割边；
$G$ 中的边割集对应 $G^$ 中的回路，$G^$ 中的回路对应 $G$ 中的边割集。

需要注意的是，对偶图的概念仅对具体的平面图成立，无法定义在任意可平面图上。事实上，两个同构的平面图的对偶图未必是同构的——同一个图的不同平面嵌入的对偶图可能并不相同。

[!example] 例子下图画了两个同构的平面图，它们的对偶图并不同构。
对偶图不同构的原因是，右图有一次面，它的对偶图有一度顶点，而左图没有。

在 OI-wiki 的计算几何模块中，对偶图思想也有直接体现：文档 Delaunay 三角剖分指出，Voronoi 图是 Delaunay 三角剖分的对偶图，可以用构造 Delaunay 三角剖分的分治算法求出三角网，再用最左转线算法求出其对偶图，从而在 $O(n\log n)$ 时间内构造 Voronoi 图。这说明"面与点互换"的对偶构造在计算几何与图论中是通用的核心思想。

实战转化：平面图最小割 → 对偶图最短路

将可平面图的问题转化到对偶图上，有时更容易解决。一个典型的例子是：可平面图最小割问题可以转化为对偶图最短路问题。设 $G$ 是带边权的可平面图，$s,t$ 是它的两个顶点，需要求最小的 $s$-$t$ 割。

具体做法是：选取合适的平面嵌入，使 $s,t$ 出现在图 $G$ 外部面边界上；添加自 $s$ 和 $t$ 延伸出去的射线，将外部面分为两部分 $f_{+}$ 和 $f_{-}$；基于该图建立对偶图，并将边权赋给对偶图中的对应边。那么，对偶图 $G^*$ 中面 $f_{+}$ 和 $f_{-}$ 对应顶点之间的路径（红色粗线）就和图 $G$ 的 $s$-$t$ 边割集（黑色粗线）一一对应，且二者权值相同。这样，求解对偶图中的最短路，就得到了图 $G$ 中的最小 $s$-$t$ 割。

一个常见的误区是根据上述转化方法宣称"平面图最小割等于对偶图最短路"。事实上，它只适用于存在 $G$ 的平面嵌入使得 $s,t$ 共面的情况，只是在考察此知识点的算法竞赛题目中，给出的图往往具有并且附带这样的平面嵌入。下面给出一个可以用于判定该条件存在性的定理。

[!note] 定理对于可平面图 $G=(V,E)$ 的两个顶点 $s,t$，存在 $G$ 的平面嵌入使得 $s,t$ 处于同一个面上，当且仅当 $(V,E\cup{(s,t)})$ 是可平面图。

证明：如果存在 $G$ 的平面嵌入使得 $s,t$ 处于同一个面上，那么就可以在这个面内添加一条边 $(s,t)$，保持图的平面性。反之，如果 $(V,E\cup{(s,t)})$ 是可平面图，那么任取它的一个平面嵌入，$s,t$ 都同处边 $(s,t)$ 所处的面；删除 $(s,t)$ 之后，$s,t$ 仍然同处一面。$\blacksquare$

例如，下图展示的情形中，添加边 $(s,t)$ 之后得到非平面图 $K_5$，故而不存在使 $s,t$ 共面的平面嵌入，上述转化不适用。

关于最小割问题本身的建模与求解（如最大流最小割定理、Dinic 实现、最小割方案输出、割边数量最小化、二者选其一与最大权闭合图等经典模型），可进一步参考 OI-wiki 的最小割文档及其配套参考代码docs/graph/code/flow/下的实现。

可平面性判定

给定一个图，如何判定它是不是可平面图？本节介绍理论基础与实用算法。

禁用图刻画

可平面图最经典的刻画方式是利用禁用图（forbidden graph）给出的。

首先，$K_5$ 和 $K_{3,3}$ 不是可平面图。

[!note] 定理 $K_5$ 和 $K_{3,3}$ 不是可平面图。

证明：前文已说明，$|V|\ge 3$ 的简单连通平面图都需要满足 $|E| \le \dfrac{l}{l-2}(|V|-2)$，其中 $l$ 是面次数的最小值。对于 $K_5$，有 $l=3,\ |V|=5,\ |E|=10$，代入得 $10 \le \frac{3}{1}\cdot 3 = 9$ 不成立，所以 $K_5$ 不可能画成平面图。对于 $K_{3,3}$，有 $l=4,\ |V|=6,\ |E|=9$，代入得 $9 \le \frac{4}{2}\cdot 4 = 8$ 不成立，所以 $K_{3,3}$ 不可能画成平面图。$\blacksquare$

事实上，它们就是使得一个图不可平面的最小结构：只要图不以某种方式包含这两个图为子结构，该图就一定是可平面的。第一个可平面性判定定理是Kuratowski 定理，它用到了图同胚的概念：

若两个图 $G_1$ 与 $G_2$ 同构，或通过反复插入或消去 $2$ 度顶点后是同构的，则称二者是同胚的（homeomorphic）。

[!note] Kuratowski 定理图 $G$ 是可平面图，当且仅当 $G$ 不含与 $K_5$ 或 $K_{3,3}$ 同胚的子图。

与此相关的另一个定理是Wagner 定理，它利用收缩操作刻画可平面图：收缩操作是指重复多次将图的一条边收缩为一个点。

[!note] Wagner 定理图 $G$ 是可平面图，当且仅当 $G$ 中没有可以收缩到 $K_5$ 或 $K_{3,3}$ 的子图。

可平面图不包含这些类型的子图相对显然，所以这两个定理的关键部分都在于相应禁用图条件的充分性。由于与 $K_5$ 或 $K_{3,3}$ 同胚的子图一定可以收缩到它们，反过来却未必成立，所以Kuratowski 定理提供了一个更弱也更容易检验的判定条件。OI-wiki 的图论基础概念一节也以"不存在与 $K_5$ 或 $K_{3,3}$ 同胚的子图"的形式引用了 Kuratowski 定理，两处表述一致。

平面性判定算法

尽管看起来并不容易，平面性判定问题实际上有很多线性时间算法。但由于这些算法的实现通常都比较复杂，它们几乎从未出现在算法竞赛中，更多出现在算法工程与图算法库的实现层面。

Hopcroft–Tarjan 算法：最早的线性时间平面性判定算法，但其实现相当复杂。
de Fraysseix–Ossona de Mendez–Rosenstiehl 算法（也称LR 平面性算法）：进一步改进了 Hopcroft–Tarjan 算法的流程，是目前最优秀的平面性判定算法之一。Python 的 NetworkX 库中就实现了这一算法（networkx/algorithms/planarity.py）。
Boyer–Myrvold 算法：同样优秀的线性时间算法。它可以在线性时间内判定给定图是否可平面；而且，如果图是可平面的，算法将输出一个平面嵌入；否则，算法将输出一个 Kuratowski 子图（即与 $K_5$ 或 $K_{3,3}$ 同胚的子图）。C++ 的 Boost 库实现了这一算法（boost/graph/planar_detail/boyer_myrvold_impl.hpp）。

更多相关算法可参考文末提供的文献。

特殊的平面图

极大平面图（平面三角剖分）

对于简单可平面图 $G$，如果在它的任意不相邻顶点间添加边，所得图都不再是可平面图，就称 $G$ 为极大可平面图（maximal planar graph）。极大可平面图的平面嵌入称为极大平面图。

[!note] 定理极大可平面图 $G$ 必然连通。而且，当顶点数 $|V|\ge 3$ 时，图 $G$ 没有割边。

证明：如果可平面图 $G$ 不连通，任选它的一个平面嵌入，都可以选择属于不同连通分支的两个顶点，在外部面内连接起来，所得图显然仍是平面图，这与 $G$ 的极大性矛盾，所以极大可平面图必连通。若 $|V|\ge 3$ 且 $G$ 有割边 $e=(u,v)$，则删去 $e$ 后 $G-e$ 恰有两个连通分支，$u,v$ 分属不同分支。假设 $v$ 所在分支至少有两个顶点，可先将 $u$ 所在分支 $G_1$ 画在平面上，选取 $G_1$ 中边界含 $u$ 的任意面 $f$，将另一分支 $G_2$ 画在面 $f$ 中。由于 $G_2$ 是简单图，其外部面边界不是自环，故至少存在另一个顶点 $w\neq u,v$。将 $v,w$ 分别连接到 $u$ 上，就得到包含 $G$ 为子图的平面图，与极大性矛盾。因此 $|V|\ge 3$ 的极大可平面图一定没有割边。$\blacksquare$

极大平面图的结构可以更准确地描述。

[!note] 定理对于顶点数 $|V|\ge 3$ 的平面图 $G$，它是极大平面图当且仅当它是简单图，且它的每个面次数均为 $3$。

证明：充分性显然。必要性：设极大平面图 $G$ 的某个面 $f$ 的边界长度至少是 $4$。由于 $G$ 无割边，该边界只能是一个环 $v_1v_2v_3v_4\cdots v_1$。若 $v_1$ 与 $v_3$ 不相邻，则在面 $f$ 内连接 $v_1$ 和 $v_3$ 不会破坏平面性，与极大性矛盾，所以 $v_1$ 与 $v_3$ 相邻；同理 $v_2$ 与 $v_4$ 相邻。但边 $(v_1,v_3)$ 和 $(v_2,v_4)$ 都不会出现在面 $f$ 中，即两条边必然在面 $f$ 的外部，而无论如何绘制这两条边都必然相交，矛盾。所以极大平面图中不存在高于 $3$ 次的面。$\blacksquare$

[!note] 推论对于顶点数 $|V|\ge 3$ 的极大平面图 $G$，总有边数 $|E|=3|V|-6$ 且面数 $|F|=2|V|-4$。

由于极大平面图中每个面都是由三条边围成，极大平面图也称为平面三角剖分（plane triangulation）。这一概念与计算几何中的三角剖分（参见 OI-wiki 的三角剖分文档）在结构上一脉相承。

外平面图

设 $G$ 为可平面图，若 $G$ 存在平面嵌入 $\tilde{G}$，使得 $G$ 中所有顶点都在 $\tilde{G}$ 的一个面的边界上，则称 $G$ 为外可平面图（outerplanar graph）。这一嵌入也称为外平面嵌入或外平面图。通常将边界经过所有顶点的那个面绘制为外部面。

外可平面图都是可平面图，反之未必成立。外可平面图同样可以使用禁用图刻画：

[!note] 定理一个图 $G$ 是外平面图，当且仅当 $G$ 中不含与 $K_4$ 或 $K_{2,3}$ 同胚的子图。

对于外可平面图，同样可以讨论极大外可平面图的概念：对于简单外可平面图 $G$，如果在它的任意不相邻顶点间添加边，所得图都不再是外可平面图，就称 $G$ 为极大外可平面图（maximal outerplanar graph），其外平面嵌入称为极大外平面图。直观上看，极大外平面图其实就是平面上多边形的三角剖分。

[!note] 定理对于顶点数 $|V|\ge 3$ 的极大外平面图 $G$，且所有顶点都在外部面的边界上，那么图 $G$ 恰有 $|V|-2$ 个内部面。

证明：对 $|V|$ 应用数学归纳法。归纳起点 $|V|=3$ 时，$G$ 是三元环，只有 $1$ 个内部面，命题成立。假设命题对 $|V|=k$ 成立，考虑 $|V|=k+1$ 的情形。

首先证明图 $G$ 一定存在 $2$ 度顶点。反设不然，将外部面边界上的顶点顺次编号，对每个 $i=1,2,\cdots,k+1$，定义 $f(i)$ 为与顶点 $i$ 连接且编号不与之相邻的顶点的最小编号。首先 $1<f(1)$。由于点 $1$ 已经与 $f(1)$ 连接，点 $2$ 与 $f(2)$ 的连线不能越过边 $(1,f(1))$，就必然有 $1<2<f(2)<f(1)$。同理 $2<3<f(3)<f(2)$。由于顶点只有有限多个，这个逐渐缩小的过程必然在有限步后终止。令 $i^$ 为满足 $1<\cdots<i-1<i<f(i)<f(i-1)<\cdots<f(1)$ 的编号 $i$ 的最大值，那么由于点 $i^$ 和点 $f(i^)$ 不相邻，必然有 $i^<i^+1<f(i^)$；而重复之前的论述仍应有 $i^<i^+1<f(i^+1)<f(i^)$，这与 $i^*$ 的最大性矛盾。故 $G$ 必然存在 $2$ 度顶点。

设 $v$ 是一个 $2$ 度顶点，删除 $v$ 得到顶点数为 $k$ 的外平面图 $G-v$，它必然是极大外平面图（否则在其上合法添加边的方法对 $G$ 也适用）。由归纳假设，$G-v$ 恰有 $k-2$ 个内部面，而删去 $v$ 恰好减少了一个 $G$ 的内部面，所以 $G$ 的内部面数目为 $k-1$。$\blacksquare$

[!note] 定理对于顶点数 $|V|\ge 3$ 的外平面图 $G$，且所有顶点都在外部面的边界上，那么 $G$ 是极大外平面图，当且仅当 $G$ 的外部面边界是长为 $|V|$ 的环，且所有内部面边界均是长为 $3$ 的环。

证明：充分性显然——连接外部面边界上的两个不相邻顶点，若连接发生在外部面中，则所有顶点无法都出现在一个面的边界上；否则连线必然与内部面的边界相交。必要性：假设外部面边界 $v_1v_2v_3\cdots v_nv_1\ (n=|V|)$ 不是环，则存在 $i\neq j$ 且 $i-j\neq\pm 1\pmod{n}$ 使得 $v_i=v_j$。不妨设 $1<i<j<n$。此时与 $v_{i-1}$ 相关联的边只能出现在回路 $v_jv_{j+1}\cdots v_nv_1\cdots v_{i-1}v_i$ 围成的有界区域内部，与 $v_{i+1}$ 相关联的边只能出现在回路 $v_iv_{i+1}\cdots v_{j-1}v_j$ 围成的有界区域内部，所以 $v_{i-1}$ 和 $v_{i+1}$ 无法相邻。可以在外部面内添加连接 $v_{i-1}$ 和 $v_{i+1}$ 的边 $e$，所得 $G+e$ 显然仍是平面图且外部面边界包含所有顶点，这与极大外平面性矛盾。所以外部面必是长度为 $|V|$ 的环；内部面边界均为长为 $3$ 的环的原因与极大平面图一致。$\blacksquare$

[!note] 推论对于顶点数 $|V|\ge 3$ 的极大外平面图 $G$，有：
$|E|=2|V|-3$；
$G$ 中至少有 $3$ 个顶点度数小于等于 $3$，且至少有 $2$ 个顶点度数为 $2$；
$G$ 的点连通度为 $2$。

仓库内的知识脉络

本仓库图论模块围绕平面图展开的知识体系相当完整，可将本文与以下文档对照阅读，形成闭环：

图论基础概念：平面图的最简定义、$|E|\le 3|V|-6$ 边数上界与 Kuratowski 定理的速查条目；
最小割：最小割的定义、最大流最小割定理、Dinic 参考代码（对应文件位于docs/graph/code/flow/）以及"二者选其一""最大权闭合图"等经典建模，是平面图对偶化转化的求解端；
最短路：对偶图最短路转化中的求解目标；
三角剖分：Delaunay 三角剖分与 Voronoi 图互为对偶图的应用实例；
插头 DP：其中提到当 $n,m\le 100$ 时可用 FKT 算法计算平面图的完美匹配数，可见"平面性"在更广泛算法问题中的价值。

习题

以下为与本主题配套的经典练习（题目名称整理自原文档，可在各 OJ 上检索）：

Luogu P3209 [HNOI2010] 平面图判定
Luogu P3249 [HNOI2016] 矿区
Luogu P4001 [ICPC-Beijing 2006] 狼抓兔子（经典的"平面图最小割转对偶图最短路"模板题）
Luogu P4073 [WC2013] 平面图
Luogu P7295 [USACO21JAN] Paint by Letters P

参考资料

Planar graph / Planarity testing（Wikipedia 相关词条）
Bondy, John Adrian, and Uppaluri Siva Ramachandra Murty.Graph Theory with Applications. Vol. 290. London: Macmillan, 1976.
Diestel, Reinhard.Graph Theory. Vol. 173. Springer Nature, 2025.
Patrignani, Maurizio. "Planarity Testing and Embedding." (2013): 1-42.
Hopcroft, John, and Robert Tarjan. "Efficient planarity testing."Journal of the ACM (JACM)21, no. 4 (1974): 549-568.
De Fraysseix, Hubert, Patrice Ossona De Mendez, and Pierre Rosenstiehl. "Trémaux trees and planarity."International Journal of Foundations of Computer Science17, no. 05 (2006): 1017-1029.
De Fraysseix, Hubert. "Trémaux trees and planarity."Electronic Notes in Discrete Mathematics31 (2008): 169-180.
Brandes, Ulrik. "The left-right planarity test." Manuscript submitted for publication 3 (2009).
Boyer, John M., and Wendy J. Myrvold. "Stop Minding Your p's and q's: A Simplified O(n) Planar Embedding Algorithm." InSODA, vol. 99, pp. 140-146. 1999.
Boyer, John M., and Wendy J. Myrvold. "Simplified O(n) planarity by edge addition."Graph Algorithms and Applications5 (2006): 241.

【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki

创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考

企业官网建设流程全解析