摘要
一个图是平面图的充分必要条件是这个图存在对偶图。那么,给定任意图,对于图中每一条支路,如果在对偶图中存在,说明这条支路可以嵌入平面;如果在对偶图中不存在,说明这条支路不能嵌入平面。这既判定了图的平面性,又给出了图的可以嵌入平面的支路。同文献〔4,5〕的算法相比,本文的算法更加简捷,降低了算法的复杂性,节省了运算时间。该算法用FORTRAN语言在MC68000机上实现,结果准确,运行速度快。
The sufficient and necessary conditions for a planar graph is that this graph must be a dual graph. So if one branch of a given graph has a corresponding branch in the dual graph, this branch could be embe-ded in the plane; if not, this branch couldn't be embeded in the plane. According to this idea, we can not only determine the plane, but also find the branches that could be embeded in the plane. Comparing with other method[4,5], this method is more simple and direct. This method has been realized successfully in FORTRAN language by using MC68000 computer.
