定义与 Kuratowski 定理
可在平面上画出而无边交叉的图。Kuratowski(1930):图是平面图 ⟺ 不含 K₅ 或 K₃,₃ 的细分。
Planar iff no K₅ or K₃,₃ subdivision.欧拉公式
对于连通平面图:V-E+F=2。可推导 E≤3V-6,意味着平面图的边数是 O(V) 的。
可在平面上画出而无边交叉的图。Kuratowski(1930):图是平面图 ⟺ 不含 K₅ 或 K₃,₃ 的细分。
Planar iff no K₅ or K₃,₃ subdivision.对于连通平面图:V-E+F=2。可推导 E≤3V-6,意味着平面图的边数是 O(V) 的。