平面图

一幅画中出现交叉，只能说明当前摆放方式不合适。顶点可以移动，边可以弯曲；可平面性问的是所有这些自由度中是否存在无交叉方案。证明不可平面需要找到对任何画法都成立的障碍，单看一张拥挤图像并不够。

抽象图与嵌入图承担不同信息。前者记录谁与谁相邻，后者还记录边如何绕过彼此、哪些边围成同一面。Euler 公式和对偶构造读取后者；平面性判定则从前者出发，寻找或拒绝一种合法嵌入。

$K_4$ 可平面。把四个顶点放在凸四边形上并画两条对角线会产生交叉，把其中一个顶点移到另外三个形成的三角形内部后，六条边即可无交叉画出。

Euler 公式理路平面图欧拉公式Euler's formula for planar graphs连通平面图的顶点数、边数与面数满足 V−E+F=2。对连通平面嵌入给出

对 $n\ge 3$ 的简单平面图，结合面边界双重计数可推出 $m\le 3n-6$。因此$K_5$理路完全图Complete graph每一对不同顶点都恰有一条边相连的有限简单无向图。 的 $m=10$ 超过 $3\cdot 5-6=9$，不可平面。这个边数界只是必要条件；满足它的图仍可能含有更隐蔽的非平面障碍。

二分平面图没有奇圈。对其含圈的块按面边界至少为四计数、对桥与森林部分单独处理，可得

$K_{3,3}$理路二分图Bipartite graph顶点可分成两个独立侧、且每条边都跨越两侧的有限简单无向图。 有九条边，而 $2\cdot 6-4=8$，所以也不可平面。它说明边数低于一般的 $3n-6$ 界仍不足以保证平面性。

把 $K_5$ 或 $K_{3,3}$ 的边细分，只是在原曲线上插入度为二的顶点，不会消除拓扑障碍。反过来，收缩这些细分路径会恢复原图。于是降低平均度或把交叉附近“拉长”都不能自动取得平面嵌入。

同一可平面图可能有多个不等价嵌入，尤其在割点或二点割存在时，可以翻转或重新排列不同块。三连通平面图则由 Whitney 定理在球面反射意义下具有唯一嵌入，这项额外连通性解释了何时面结构接近抽象图的不变量。

可平面性在取子图理路子图Subgraph从母图删除顶点或边、同时保留剩余边端点关系所得的图。和minor理路图 minorGraph minor · Minor of a graph通过删顶点、删边和收缩边从原图获得的粗粒度图结构。时保持。Kuratowski 定理理路Kuratowski 定理Kuratowski's theorem有限图可平面嵌入，当且仅当不含 K5 或 K3,3 的细分子图。断言有限图可平面，当且仅当它不含 $K_5$ 或 $K_{3,3}$ 的细分子图；Wagner 定理把“细分子图”换成这两张图的 minor。两条刻画结论等价，证书对象却不同。

若图有 $c$ 个连通分量理路图连通性Graph connectivity用顶点间是否存在路径定义无向图的连通性，并由此划分连通分量。，平面嵌入满足

所有分量共享一个外面，所以不能把每个分量的面数直接相加而不校正。桥会在同一面边界游走中被经过两次，面度计数必须按边侧而非肉眼看到的多边形边数进行。

固定嵌入后，可以为每个面放置一个对偶顶点，并让原图每条边对应一条跨越它的对偶边。割与圈由此交换角色，平面网络流、最短路和地图着色可以利用对偶结构；只知道抽象图“可平面”还不足以指定哪一个对偶图。

对非空简单平面图，稀疏性配合握手引理理路握手引理Handshaking lemma有限无向图中所有顶点度数之和等于边数的两倍。推出平均度小于六，因此必有度数至多五的顶点，支持删除—回插式归纳。图绘制、印刷电路布线与地理邻接建模还会加入直线边、几何位置或层数限制；Fáry 定理保证简单平面图存在直线无交叉画法，但固定顶点坐标后结论不再自动成立。