L013 平面

可平面图

对于图 \(G=\langle V,E\rangle\)，将 \(G\) 画在平面上的「画法」（drawing）是一个单射函数 \(dr\)，其将每个顶点 \(v\in V\) 映射到平面上的一个坐标点 \(dr(v)\)；将每条边 \((u,v)\in E\) 映射到平面上的一条 \(dr(u)\)-\(dr(v)\) 曲线。

若边集中任意两条边映射到的平面曲线不交叉，即没有除了端点以外的公共坐标点，则称 \(G\) 为「可平面图」（planar graph），\(dr\) 称作 \(G\) 的一个「平面嵌入」（planar embedding），映射到平面上的结果称作 \(G\) 的一个「平面图」（plane graph）；否则称 \(G\) 为「不可平面图」（non-planar graph）。

平面图 \(H\) 将平面分割出的极大相连区域（不含平面图自身）称作 \(H\) 的「面」（face），面积无限的面称作「无限面」（unbounded face），也称「外部面」（outer face）；面积有限的面称作「有限面」（bounded face），也称「内部面」（inner face）。

平面图 \(H\) 的面的数量称作 \(H\) 的「面数」（number of faces），记作 \(\phi(H)\).

Th.10.1 Cor.10.1

图 \(G\) 的平面图 \(f\) 的「长度」（length）是从平面分割出的 \(f\) 中的 \(G\) 的闭路线长度的和，记作 \(l(f)\).

Th.10.2-10.3 Cor.10.2

Th.10.4-10.5

「DMP 算法」（DMP algorithm, Demoucron-Malgrange -Pertuiset algorithm）、「片段」（fragment）、「固定点」（vertex of attachment）。

Th.10.6

面的染色

「对偶图」（dual graph）、「\(k\) 面染色」、「正常 \(k\) 面染色」、「\(k\) 面色可染」、「面色数」。

Th.10.7-10.10

「可约构形」（reducible configuration）、「不可避免集」（unavoidable set）。