图论/平面图

平面图

定义

平面图是指可以在平面上绘制的图，没有边交叉。

特征

平面图可以通过一个定理来描述，该定理最初由波兰数学家卡齐米日·库拉托夫斯基在1930年证明，现在被称为库拉托夫斯基定理。

• 有限图是平面图，当且仅当它不包含一个子图，该子图是 $K_{5}$ 或 $K_{3,3}$ 的细分。

图的细分是通过在边中插入零个或多个顶点得到的。

瓦格纳定理处理的是次图，而不是细分。

• 有限图是平面图，当且仅当它没有 $K_{5}$ 或 $K_{3,3}$ 作为次图。

如果可以通过重复删除边和/或边收缩从图 G 中获得图 H 的副本，则图 H 是图 G 的次图。