可平面图(planar graph)是一类特殊的图，指同构于某一平面图的图。如果一个图能够画在平面上，使得顶点集合及边集合分别是相同的，而如果边相交仅在边的端点处，则称这个图是可嵌人平面的，或称作可平面图(planar graph)；否则称作不可平面图，可平面图G的这样一种画法称为G 的一个平面嵌入(planar embedding)。库拉托夫斯基定理给出了可平面图的特徵，其内容为：图G是可平面图若且唯若G没有同胚于完全图K5和完全二部图K3,3的子图，同胚于K5和K3,3的图称为库拉托夫斯基图。这一定理是由库拉托夫斯基(Kuratowski，K.)于1930年证明的，若可平面图G不是任何同阶其他可平面图的子图，则称G为极大可平面图，极大可平面图所对应的平面图的每个面都必为三角形；同构于外平面图的图称为外可平面图；3正则的可平面图称为3正则平面图；G是外可平面的若且唯若G没有与完全图K4同胚的子图。
基本介绍
- 中文名：可平面图
- 外文名：planar graph
- 别名：可嵌人平面的
- 所属学科：离散数学
- 相关概念：平面图、欧拉公式等
- 相关定理：库拉托夫斯基Kuratowski定理
定义
如果一个图能够画在平面上，使得顶点集合及边集合分别是相同的，而如果边相交仅在边的端点处，则称这个图是可嵌人平面的，或称作可平面图(planar graph)；否则称作不可平面图，可平面图G的这样一种画法称为G 的一个平面嵌入(planar embedding)。
如果一个可平面图重新画在平面上，使得没有两条边相交，除非在顶点处，则称这个图是平面图(plane graph)。
相关性质定理
平面图的度定理
设G是平面图，记m是G的边数，则
证明:图中的一条割边是关联一个面的，对该面的度贡献为2；一条非割边是关联两个不同的面的，并分别对这两个面的度贡献为1，因此，将所有面的度求和时，每条边用了两次。
平面图的欧拉公式及其套用
不难发现，在连通平面图中有一个关于顶点、边及面的数目的简单公式，因为欧拉(Euler)首先对多面体的顶点和边所定义的平面图建立了这个公式，所以该公式以欧拉命名。
平面图的欧拉公式： 设G是无向连通平面图，具有n 个顶点，m条边和r个面，则 n-m+r=2。
推论1如果G是平面图，则n-m+r=w+1，其中，w是G的连通分支数。
推论2 一个连通可平面图的所有平面嵌人都有相同的面数。
证明：这是因为一个连通可平面图的所有平面嵌人都是彼此同构的，因此在顶点数、边数都分别相同的情况下，利用平面图的欧拉公式，直接证得。
推论3如果G是顶点数大于等于3的简单可平面图，则m≤3n－6。
推论4 K5是不可平面图。
证明：因为K5是顶点数为5的简单图，其m=10，n=5，3n－6 =9，有m>3n- 6，由推论3，得证K5是不可平面图。
推论5K3,3是不可平面图。
证明：利用K3,3是一个简单的二部图，其任一个迴路的长度至少是4，如果它是可平面图，其边数应小于等于2n-4，但是，K3,3的n=6，m=9，2n-4=8，m>2n-4，所以K3,3是不可平面图。
推论6
如果G是简单的可平面图，则
其中
表示图G的最小度。
可平面图的判定
虽然欧拉公式可用来判别某个图是不可平面图，但是当顶点数和边数较多时，套用欧拉公式进行判别就会相当困难。一个图是否有平面的图形表示是判别可平面图的最具说服力的方法，但是又因为工作量太大而不实用，要找到一个好的方法来判断任意一个图是否是可平面图，就得对平面图的本质有所了解，已经分别证明了K5和K3,3是不可平面图，而它们的任何真子图却是可平面图，波兰数学家库拉托夫斯基(Kuratowski，1930)给出了平面图的一个异常简单的特性。
细分
设G是一个无自环边的无向图，去掉它的一条边{u，v}，并且用两条新的边{u,w}和{w,v}替换它，其中，顶点w不是图G 的顶点，通过添加每个度为2的一个或多个新的顶点，按照这样的方法得到的新图，称作G 的细分(subdivision)。
显然，如果一个图G是可平面图，那幺G的每个细分也是可平面图；并且如果图G是不可平面图，则G的每个细分也是不可平面图。
库拉托夫斯基Kuratowski定理
一个图G是不可平面图的充分必要条件是G 包含K5或K3,3，或者K5或K3,3的细分作为它的子图。
由于该定理的证明比较複杂，所以在此省略。
