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