摘要
Malgrange、Malgrange和Pertuiset三人合作提出O(n2)时间复杂度的平面性判断算法,尽管效率不是那么理想,却易于理解,并且算法结束时能够给出平面图的一种平面嵌入,另外算法仅涉及到割点的检测、图的计算机表示、图的分割、图的遍历等较为基础的问题,从而能够很好地适应教学及入门对直观性,可实现性的需要。尽管这个方法已经较为直观,但是由于图的平面嵌入在计算机中的表示较为困难等问题,其算法具体如何实现依然需要细心研究。
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.
出处
《现代计算机》
2012年第5期11-13,共3页
Modern Computer
关键词
图论
平面性判断
平面嵌入
割点
Graph Theory
Planarity Testing
Planarity Embedding
Cut Vertex
