平面图 (图论)

库拉托夫斯基定理

1930年，波兰数学家卡齐米日·库拉托夫斯基提出的一类禁用准则（指满足某种条件的图就一定无法具有某个性质）中，包括了平面图的情况。这个定理现在被称作库拉托夫斯基定理：

一个简单图是平面图当且仅当它并不包含一个是 K₅ 或 K_3,3 的分割的子图^[2]。

其中， K₅ 代表有 5 个点的完全图，K_3,3 代表两部分各 3 个点的完全二分图，分割的定义如下。考虑一个作用，将一个边中间插入一个顶点，如下图

可以将图 B 做有限次的上述操作可以得到图 A，则称 A 是 B 的细分图^[4]。

用图的同胚理论来说，就是一个有限图是平面图当且仅当这个图不包含任何同胚于${\displaystyle K_{5}}$ 或${\displaystyle K_{3,3}}$ 的子图。

这个定理的一般化是罗伯森－西摩定理。

华格纳定理

在随后的1937年，德国数学家克劳斯·华格纳（英语：Klaus Wagner）提出了类似的禁用定理，华格纳定理：

一个简单图是平面图当且仅当它不是 K₅ 或 K_3,3 的次图。

其中，一个图的次图是将它做有限多次的取子图(删除部分顶点和边)和做边收缩（英语：edge contraction）(将某边缩成一个顶点)所得到的图。

平面图和球面嵌入

说一个图是平面图，其实等价于说存在一个从空间到平面的连续的单射，能够将这个图投射到平面上。从这样的角度看来，平面图是空间的一部分在二维平面上的一个嵌入。然而，图在二维平面的嵌入和在球面的嵌入是等价的：

能够画在平面上的图，必然也能画在球面上，使得不同的边互不交叠，反之亦然。

证明是显而易见的：首先，如果一个图是平面图，那么将它画在一张纸上，并在“墨迹未干”之时将这张纸“拓印”在一个足够大的球面上（这样纸基本不会皱）。于是，就得到了一个画在球面上的同样的图。反过来，如果能把一个图画在球面上而没有交互重叠的边，那么，把球放在一个无限大平面上，并将球稍作滚动，使得球的最高点不在图的边或顶点上。然后，以最高点为中心，把球面（出了最高点）投影在平面上，那么，得到的平面图形和原来的图是一样的，而且没有交互重叠的边，所以原来的图也是平面图。

依此准则，空间中的各种凸多面体对应的图都是平面图，因为只要在多面体的内部找一个合适的球，然后将多面体的顶点和边都投影在这个球面上，就完成了相应的图在球面的嵌入（由于多面体是凸的，投影得到的图形的边之间不会交叠）。比如说，所有的正多面体对应的图都是平面图^[2]。

实务上，用库拉托夫斯基定理来判别一个图的平面性是很费时的。然而，给一个 n 个顶点的图，目前已经能用 O(n) 的时间(线性时间)来判别该图是否是平面图，参见英文维基条目 planarity testing（英语：planarity testing）。以下列出了常见的平面性判别法。

• 惠特尼平面性判别法（英语：Whitney's planarity criterion）根据代数对偶的存在性给出了平面性的一个刻划。
• 麦克兰恩平面性判别法（英语：Mac Lane planarity criterion）根据平面图的循环空间（英语：cycle space）给出有限平面图的代数刻划。
• 左右平面性判别法（英语：Left-right planarity test）根据深度优先搜索树的 cotree 边的二部性给出平面图的一个刻划，此判别法是左右平面性测试算法的核心理论。
• 施尼德定理（英语：Schnyder's theorem）用偏序集维度（英语：order dimension）表达出一个平面性的刻画。
• 科兰·德·韦迪耶尔平面性测试（英语：Colin de Verdière graph invariant）用图的哈密顿算符的第二个特征值的最大重数刻划平面性。
• 哈纳尼-塔特定理（英语：Hanani–Tutte theorem）：一个图是平面图当且仅当他可以被画在平面上，使得任两相异边交叉偶数次。因此有时可以借由模 2 简化平面性系统的研究。

一个平面图将平面分成若干个互不相通的封闭区域，以及图的外部的区域。其中，图的外面的区域称为图的外部面，而图里面每个被顶点和边分割出来的封闭并连通的区域称为图的内部面。围成每个面图的每个面至少对应着三条边。

平面图的顶点个数、边数和面的个数之间有一个以大数学家莱昂哈德·欧拉命名的公式：

${\displaystyle V-E+F=C+1}$ 

其中，V是顶点的数目，E是边的数目，F是面的数目，C是组成图形的连通部分的数目。当图是单连通图的时候，公式简化为：

${\displaystyle V-E+F=2}$ 

以前面表格提及的蝶形图为例，有 V = 5，E = 6，且 F = 3。

若 ${\displaystyle G}$ 是连通的简单平面图，则每个面都由至少 3 个边围成，且每个边仅触及 2 个面，因此有 ${\displaystyle 3F\leq 2E}$ ，代入上式可得

${\displaystyle E\leq 3V-6}$ 

由此可知，平面图的边是很稀疏 的。通过讨论 ${\displaystyle G}$ 的各连通部分可知上式对一般的简单平面图 ${\displaystyle G}$ 都成立。

事实上，欧拉公式对于空间中的凸多面体也适用，而这并不是巧合。因为凸多面体可以借由施莱格尔图（英语：Schlegel diagram）的投影方式投影至平面形成一个连通的简单平面图，而施莱格尔投影是透视投影，他的透视中心可以选在凸多面体的任一一个面上的点。但并不是所有的连通简单平面图都是凸多面体的投影，例如树即为反例。斯坦尼茨定理（英语：Steinitz's theorem）表明一个图是个凸多面体的施莱格尔图当且仅当它是 3-连通的简单平面图。

一个多于一条边的连通平面图满足不等式 ${\displaystyle 2e\geq 3f}$ ，因为每个面至少有三条有效边且每条边都肯定分割两个面。结合欧拉公式 ${\displaystyle v-e+f=2}$  我们可以得到平面图的平均度数是严格小于6的。如果一个图的度数大于等于6，那么一定不是平面图。

硬币图

一个硬币图的顶点是由许多圆的圆心组合而成，这些圆两两外切或外离，两顶点之间连边当且仅当以两顶点唯圆心的两圆外切。1936 年，保罗·克伯（英语：Paul Koebe）首次证明填装球定理（英语：circle packing theorem）：一个图是平面图当且仅当它是一个硬币图。

法里定理（英语：Fáry's theorem）是填装球定理（英语：circle packing theorem）的一个直接推论，叙述是每个平面图都可以被画在平面上，使得各边对应到不相交的线段。事实上，只要考虑平面图对应到的硬币图，以圆心为顶点，以两相切的圆的圆心连线段为边，则所以得边是不会相交的。

极大平面图

一个简单图被称作是极大平面图如果他是平面图而且任加一条边再不相邻的顶点上都会得到非平面图。所以，极大平面图所有的面，包括外围面在内，都恰好被三条边包围，因此，极大平面图又被称为平面三角分割。所有极大平面图都是3-连通（英语：3-vertex-connected）的。

一个包含 v 点的极大平面图 (v>2) 恰有 3v-6 条边和 2v-4 个面。

在原本一个大三角形的内部加一个点并与三点连上边，也就是将大三角形分割成三个小三角形。不断的重复上述步骤，所得到的图称为阿波罗尼奥斯网络（英语：Apollonian networks），是极大平面图的其中一类。事实上，阿波罗尼奥斯网络是一个平面的3-树（英语：3-tree）。

所有末梢环（英语：peripheral cycle）都是三角形的图称为绞窄图（英语：Strangulated graph）。因为平面图的导出环是一个面，所以末梢环也是。于是推得极大平面图是绞窄图。

外围平面图

外围平面图是一个平面图满足存在一个画在平面上的方法使得外围面的边界包含所有顶点，该画法被称为该图一个外围平面嵌入。外围平面图一定是平面图但反过来不一定成立，例如完全图 K₄ 是平面图但并非外围平面图。库拉托夫斯基定理友在外围平面图上的版本：一个图是外围平面图当且仅当它并不包含一个是 K₄或 K_2,3 的分割的子图。事实上，该版本是下述事实的直接推论：图${\displaystyle G}$ 是外围平面图当且仅当在${\displaystyle G}$ 外面加一个顶点，连边到${\displaystyle G}$ 的所有顶点，所得到的图是平面图^[5]。

图的 1-外围平面嵌入是一般的外围平面嵌入。对所有 k>1，一个图的平面嵌入是 k-外围平面嵌入当且仅当将他删掉外围面边界上的所有顶点会形成一个 (k-1)-外围平面嵌入。一个图如果有一个 k-外围平面嵌入则被称为是一个 k-外围平面图。

不环绕嵌入图

所有图都可以被嵌入三维空间中使得各边不交叉，特别的，如果该图存在一个嵌入额外满足图中的两个互斥环对应到三维空间中的两个互不环绕的封闭曲线(环绕数为0)，则该图被称为是一个不环绕嵌入图（英语：linklessly embeddable graphs）。不环绕嵌入图可以被看做是平面图的三维空间版本，所以也有类似华格纳定理的禁用结果：一个简单图是平面图当且仅当它不是佩特森图族（英语：Petersen family）中所有的 7 个图之一的次图。类似的，平面图和外围平面图分别对应到科兰·德·韦迪耶尔不变量（英语：Colin de Verdière's planarity criterion）小于等于 2 和 3 的图，而环绕嵌入图对应到科兰·德·韦迪耶尔不变量小于等于 4 的图。

哈林图

哈林图是一个平面图，是将一个不包含度数为 2 的顶点的树的叶子由一个环连结起来所得到的图。等价的，哈林图是一个多面体图（英语：polyhedral graph）满足有一个面与其他所有的面都相邻。如同外围平面图，哈林图的树宽值（英语：treewidth）也很低，因此哈林图相关的算法问题会比一般的平面图来的好处理许多^[6]。

其他相关的图

一个图是尖点图（英语：apex graph）如果它可以删去某一个顶点之后变成平面图，一个图是 k-尖点图如果如果它可以删去某 k 个顶点之后变成平面图。

一个图是1-平面图（英语：1-planar graph）如果它可以画在平面上使得每条边至多和所有其他边交叉一次，一个图是 k-平面图如果它可以画在平面上使得每条边至多和所有其他边交叉 k 次。

给定一个地图，满足上面的各个区域都是单连通且两两只在边界上有交集。将各个区域视为顶点，两区域的边界若有交集则连边，所获得的图称为地图图（英语：map graph）。如果在原地图上，至多三个区域有共同交集，则定义出来的地图图是平面图，但若存在四个以上的区域相交在同一个点上，在定义出来的地图图可能是非平面图。

一个图被称为环面图（英语：toroidal graph）如果它可以被嵌入环面使得各边不交叉。更广义的来说，一个图的亏格被定义为所有该图可以嵌入而边不交叉的曲面中亏格的最小值。因此，平面图的亏格为 0 而非平面的环面图的亏格为 1。

一个向上平面图（英语：upward planar drawing）是可以被画在平面上的有向无环图，使得各个有向边都是斜向上的。并不是所有平面有向无环图都是向上平面图，事实上，决定任意给定有向图是否为向上平面图的难度是 NP完全的。

若将顶点标号，有 n 个顶点的平面图的数量的渐近式由${\displaystyle g\cdot n^{-7/2}\cdot \gamma ^{n}\cdot n!}$ 给出，其中常数${\displaystyle {\displaystyle \gamma \approx 27.22687}}$ 、${\displaystyle {\displaystyle g\approx 0.43\times 10^{-5}}}$ ^[7]；若不将顶点标号，有 n 个顶点的平面图的数量则界在 ${\displaystyle 2.72^{n}}$ 和 ${\displaystyle 30.06^{n}}$ 之间。

几乎所有的平面图的自同构数量随着顶点数的增加呈现指数增长^[8]。

四色定理叙述说任何平面图都可以被 4-着色。

法里定理（英语：Fáry's theorem）说所有简单平面图都从在一种平面嵌入法使得各边对应到互相不相交的线段，在平面上一个有 n 点地集合被称为泛顶点集（英语：universal point set）如果所有 n 点的平面图都可将顶点对应到它们，而且边是互不相的直线。例如 4 个顶点的泛顶点集是所有满足其中一个点在另外三个点围成的三角形的内部。任何外围平面图可以被画在平面上满足所有顶点在给定的圆上面，所有边是互不相的直线且都落在圆里面。

一个平面图被称作是凸 的如果他可以被画在平面上，使得各个面，包括外围面，都是凸多边形。一个图是凸平面图当且仅当它是一个3-连通（英语：k-vertex-connected graph）平面图的分割。

谢纳曼猜想（英语：Scheinerman's conjecture） (现在是定理) 说所有平面图都可以表示成平面上一些线段的交集图（英语：intersection graph）。

平面图分离定理（英语：planar separator theorem）说给定任何包含 n 个顶点的平面图，都可以借由移除至多 ${\displaystyle O({\sqrt {n}})}$ 个点来将原图分开成两个部分，并且各部分的顶点数不超过 ${\displaystyle {\frac {2}{3}}n}$ 个。由此可推得平面图的树宽值（英语：treewidth）和分支宽值（英语：branch-width）至多 ${\displaystyle O({\sqrt {n}})}$ 。

存在复杂度为 O(n) 算法来判断两个 n 点的平面图是否同构，参见图同构问题^[9]。

欧式图是一个以平面上的点以及之间用欧几里得距离的边连接的图。

网格化系数（英语：Meshedness coefficient）定义为一个平面图的面个数除以 2n-5 (平面图最大的面数）。所以网格化系数最小是0（树），最大是1。

单词可表（英语：Word-representable graph）平面图包含了一个没有三角形的平面图，更一般的说，是可3着色的平面图。

设 G 是一个平版图，G 不见得是简单图，定义 G 的对偶图 G* 如下述。在 G 中的每个面 (包括外围面) 取一个点，作为 G* 的顶点，对于 G 中的每个边 e，画一条 G* 中的边 e* 连接与 e 相邻的两个面中的顶点，而且 e* 要穿过 e。如果与 e 相邻的两面是同一个，则对该面中的点画一个穿过 e 的自环，如果 G 中两相邻面的交界包含多个边，则 G* 中的两点之间要连多条边，如右图。

此时对偶图 G* 也是平版图，而且如果 G 是连通的，则 G** 与 G 在球面上是拓朴等价的，换句话说，他们是相同的平面映射。如果 G 是多面体 Γ 对应到的多面体图，则 G* 是 Γ* 对应到的多面体图，其中 Γ* 是 Γ 的对偶多面体。

对偶图的重要性在于，对偶图和原图的性质的关系往往是易于刻划的，因此，有时研究一个平版图 (或平面图) 的对偶图的性质有助于对原图的了解。注意到，一个平版图的对偶图在拓朴等价下是唯一的，但一个平面图可能有多种平面嵌入的方式，因此可能会对应到多个不同的对偶图。

1. ^ Trudeau, Richard J. Introduction to Graph Theory Corrected, enlarged republication. New York: Dover Pub. 1993: 64 [8 August 2012]. ISBN 978-0-486-67870-2. （原始内容存档于2019-05-05）. Thus a planar graph, when drawn on a flat surface, either has no edge-crossings or can be redrawn without them. 
2. ^ ^{2.0 2.1} 王树禾. 《圖論》. 科技出版社. 2004. ISBN 9787030124234. 
3. ^ 演算法觀點的圖論. 教科书. 国立台湾大学出版中心出版. 2017: 142 [2019-05-10]. ISBN 9789863502586. （原始内容存档于2021-04-13）. 
4. ^ 算法观点的图论, 2017^[3], p.142
5. ^ Felsner (2004).
6. ^ Sysło, Maciej M.; Proskurowski, Andrzej, On Halin graphs, Graph Theory: Proceedings of a Conference held in Lagów, Poland, February 10–13, 1981, Lecture Notes in Mathematics 1018, Springer-Verlag: 248–256, 1983, doi:10.1007/BFb0071635 .
7. ^ Giménez, Omer; Noy, Marc. Asymptotic enumeration and limit laws of planar graphs. Journal of the American Mathematical Society. 2009, 22: 309–329. Bibcode:2009JAMS...22..309G. arXiv:math/0501269  . doi:10.1090/s0894-0347-08-00624-3. 
8. ^ McDiarmid, Colin; Steger, Angelika; Welsh, Dominic J.A. Random planar graphs. Journal of Combinatorial Theory, Series B: 187–205. CiteSeerX 10.1.1.572.857  . doi:10.1016/j.jctb.2004.09.007. 
9. ^ I. S. Filotti, Jack N. Mayer. A polynomial-time algorithm for determining the isomorphism of graphs of fixed genus. Proceedings of the 12th Annual ACM Symposium on Theory of Computing, p.236–243. 1980.

• Planarity （页面存档备份，存于互联网档案馆）：通过改变顶点的位置，令图的边互不重叠的游戏