平面图的判定在离散数学中是一个重要的研究领域，它不仅涉及图论的基本概念，还与拓扑学、计算机科学等学科有着密切的联系。平面图是指可以嵌入到平面上的图，使得其边不相交。判定一个图是否为平面图是离散数学中的一个重要问题。

### 1. 平面图的基本概念

平面图是指一个无向图G=(V,E)，其中V是顶点集，E是边集，且该图可以嵌入到平面上，使得其边不相交。如果一个图不能嵌入到平面上而不使任何两条边相交，则称该图为非平面图。

### 2. 平面图的判定方法

#### 2.1 Kuratowski定理

Kuratowski定理是判定一个无向图是否为平面图的一个重要定理。该定理指出，一个无向图是平面的当且仅当它不包含与K5（完全五边形）或K3,3（完全二部三边形）同胚的子图。这里所说的同胚是指通过连续变形（不改变图形结构）可以将一个子图变为另一个子图。

#### 2.2 Euler公式

对于连通的平面简单有向图G=(V,E)，如果G有n个顶点、m条边和f个面，则Euler公式给出：\[ n - m + f = 2 \]利用这个公式可以帮助我们验证一个给定的简单有向图是否为平面的。

#### 2.3 深度优先搜索（DFS）

通过深度优先搜索算法，我们可以检查给定的无向图是否能够被嵌入到平面上而不使任何两条边相交。具体地，我们可以使用DFS来尝试将每个顶点依次放置在平面上，并检查每次添加新顶点时是否会与已放置的顶点或边上发生交叉。

### 3. 平面性的应用

判断一个图形是否为平面图形对于解决许多实际问题至关重要。例如，在电路设计中，确定电路板上的布线是否可能不相交是一个重要的问题；在地图绘制中，确保地图上的线条不会交叉也是关键问题之一。

### 4. 结论

综上所述，判定一个无向图为平面图形的方法多种多样，包括Kuratowski定理、Euler公式以及基于深度优先