图是一个抽象数据结构,常用于为信息结构建模。图能够为现实世界中对象的任意信息建模,表示对象和对象之间的关联关系。　　 平面图在图论和图形绘制中担任着重要的角色。长期以来,平面图理论在印制电路板的设计和大规模集成电路的布线方面有着重要应用。目前,数据可视化的应用日益广泛,如可视化数据挖掘,网络的可视化等,平面图也有非常大的作用。　　 平面图是所有边都不交叉的图。平面图问题包括两部分:图的平面性判定和平面图绘制。图的平面性判定判断一个图是否能以平面形式绘制。平面图绘制是如何以平面形式绘制一个图,即理论上是平面的图在实际绘制时能否以平面方式画出。本文不讨论平面图绘制的问题。　　 如果一个图能够画在一个平面上,除了边的端点以外,没有边交叉,这个图就是平面的。Kurtowski指出一个图G是平面的,充分必要条件是图G中不包含任何子图为K5型图和K3,3型图。这就是著名的Kurtowski定理。Kurtowski定理的理论意义很强,但是在计算机上用Kurtowski定理进行平面性判定,算法复杂性很高,也不易于实现。一般不使用。　　 本文研究了计算平面图节点st-编号的算法,并研究了st-编号的丛形式。在此基础上,研究了PQ树构造算法,实现了用PQ树构造算法进行了图的平面性判定。　　 图的平面性判定算法都是一些很复杂的算法,实现起来比较困难。本人对算法进行了认真的分析,耐心的调试,不但从理论上阐述了这些算法,并实现了这些算法。　　 在本课题中,本人还参与了可视化技术开发平台的研究与开发工作,使这些算法在平台中得到有效应用。