关键词: 平面性, 辅助图, 三元图

Abstract:

In the 1970s, Liu Yan-Pei obtained a sufficient and necessary condition to determine whether a graph isplanar by auxiliary graph.The signed triple graph characterizes the inner construct of a graph.Meanwhile, usingsigned triple graph, one can decide whether a graph is planar or nonplanar.In this paper, the equivalence of auxiliarygraph and signed triple graph is proved.Furthermore, it is pointed out that the method by auxiliary graph is superiorto that by signed triple graph in view of complexity.

Key words: planarity, auxiliary graph, triple graph