平面图 (图论) 编辑
在图论中，平面图是可以画在平面上并且使得不同的边可以互不交叠的图。而如果一个图无论怎样都无法画在平面上，并使得不同的边互不交叠，那么这样的图不是平面图，或者称为非平面图。完全图 K5和完全二分图 K3,3是最“小”的非平面图。
1
相关
库拉托夫斯基定理是一个关于平面图的等价判定定理，它由波兰数学家卡齐米日·库拉托夫斯基提出。这个定理表明，一个图是平面图当且仅当它不包含K5 或 K3,3的细分。其中，K5是包含5个顶点的完全图，K3,3是包含6个顶点的完全二分图，其中三个顶点和另外三个顶点两两相连，K3,3也被称作utility graph。
多面体图是几何图论的一个概念，指凸多面体的顶点、边构成的图。在图论中，多面体图均为3-连通平面图。
在图论，交叉数




cr




{\displaystyle {\text{cr}}}

是将图



G


{\displaystyle G}

画在平面上时，边的交叉点的最小数目。若





cr



=
0


{\displaystyle {\hbox{cr}}=0}

，则



G


{\displaystyle G}

称为平面图。在图形制图方面，计算图的交叉数仍是一个重要问题，因为读者研究发现，画图的交叉越少，越有利于读者理解。