Welcome to Journal of University of Chinese Academy of Sciences,Today is

›› 2004, Vol. 21 ›› Issue (4): 451-453.DOI: 10.7523/j.issn.2095-6134.2004.4.004

Previous Articles     Next Articles

Equivalence of Auxiliary Graph and Signed Triple Graph

WEI Er-Ling   

  1. Department of Mathematics, Renmin University of China, Beijing 100872, China
  • Online:2004-07-10

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

CLC Number: