用PQ-树算法判定图的平面性

有效的平面性判定算法在许多领域都有应用。本文介绍了“顶点添加”判定算法、PQ-树算法及用PQ-树算法线性实现“顶点添加”法。在我们的实现中,对于平面图还给出了它们的一种平面嵌入。