一种简单的图的平面性判断算法的实现研究

Malgrange、Malgrange和Pertuiset三人合作提出O（n2）时间复杂度的平面性判断算法，尽管效率不是那么理想，却易于理解，并且算法结束时能够给出平面图的一种平面嵌入，另外算法仅涉及到割点的检测、图的计算机表示、图的分割、图的遍历等较为基础的问题。从而能够很好地适应教学及入门对直观性，可实现性的需要。尽管这个方法已经较为直观。但是由于图的平面嵌入在计算机中的表示较为困难等问题．其算法具体如何实现依然需要细心研究。

Research on the Implementation of One Simple Figure Planarity Testing Algorithm

Designs this planarity testing algorithm with O（n2） time complexity by Malgrange, Malgrange and Pertuisct. Though the algorithm is not quite effective, it has the advantage of easily understanding, which make it possible to be coded by beginners of graph theory. Furthermore, the algorithm would also give the planar embedding of the graph if it is a planar one. The algorithm only invoke the basic knowledge of cut vertex finding, presentation of graph, traversal of graph, so as to satisfy the need of teaching and learning of beginners. Despite its simplicity, the algorithm also encounters problems of representation of graph embedding and so on, which needs to be considered carefully.