平面性算法(planarity algorithm)是图论中的一种重要算法，是指判定一个给定图是否为可平面图，并且求出它的一个平面嵌入(若是可平面图)在计算机上可以实现的方法。第一个平面性算法是由奥斯兰德尔(Auslander，L.)和帕特尔(Parter，S.V.)于20世纪60年代初给出的。之后，出现了有数十种之多的算法。直到1974年，由候波科劳(Hopcroft，J.)和塔尔金(Tarjan，R.)建立了第一个线性时间的算法，即对很大的图这个算法所需的计算时间以图的顶点数的一个线性函数为上界1。

基本介绍平面性算法(planarity algorithm)是一种求平面嵌入的算法，指判断一个给定的图是否是可平面图，并且如果它是可平面图，则要找出它的平面嵌入来。设H是图G的一个可平面子图， 是H在这个平面中的一个嵌入，若G是可平面图，且存在G的一个平面嵌入 ，使得 ，则称 是G容许的。例如，图1表示G的一个平面子图的两个嵌人；一个是G容许的，而另一个则不是。

若B是H(在G中)的任意一座桥，且B对于H的接触点都包含在 的面 的周界上，则称B在 的面 内是可画的。用 表示在 中桥B是可画出的那些面的集。

相关定理平面性算法是基于如下定理：

若 是容许的，则对于H的每座桥B， 。

**证明：**若 是G容许的，则根据定义，存在G的一个平面嵌入 ，使得 。显然，H的桥B所对应的 的子图必然限制在 的一个面中，因此 。

由于一个图是平面图当且仅当它的基础简单图的每个块都是平面图，所以只要考察简单块就够了。给定这样的一个图G后。算法就确定了G的一个平面子图的递增序列 ，以及对应的平面嵌入 ，终止于G的一个平面嵌入。对每一步，都应用定理的必要条件，来判断G的非平面性2。

具体过程步骤如下：

1.设 是G的一个圈，找出 的一个平面嵌入 ，置 ；

2.若 ，则停止；否则，确定G中 的所有桥；对于每座这样的桥B，找出集 ；

3.若存在一座桥B，使得 ，则停止，根据定理，G是非平面图，若存在一座桥B，使得 ，则令 ，否则令B是任一座桥，且 是任一使得 的面；

4.选择一条连结B对于 的两个接触顶点的路 ，置 ，并把 画在 的面 内，得到 的一个平面嵌 ，令 ，转入步骤2。

这个算法是一个有效算法，它的主要运算包括：

(i) 找出图G中的一个圈 ；

(ii) 确定G中 的桥以及它们对于 的接触顶点；

(iii) 对于 的每个面 确定 ；

(iv) 对于 的每座桥B，确定 ；

(v) 在G的某座桥B中求 的两个顶点之间的一条路P；

上述每一个运算都存在有效算法，因此，这个算法是一个有效算法。继这个方法之后，许多研究者都致力于这种平面性算法的研究并提出了一些算法。

应用举例

为了说明这个算法，考察图2中的图G，从圈 和G的一张桥的表开始(为了简洁起见，桥用其边集来表示)；在每一步中。对于 的桥B以粗体字标出。这个例子中，算法终止于G的一个平面嵌入 ，所以G是平面图。

|| ||

本词条内容贡献者为:

尚华娟 - 副教授 - 上海财经大学