›› 2004, Vol. 21 ›› Issue (4): 451-453.DOI: 10.7523/j.issn.2095-6134.2004.4.004
Previous Articles Next Articles
WEI Er-Ling
Online:
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:
O157.5
WEI Er-Ling. Equivalence of Auxiliary Graph and Signed Triple Graph[J]. , 2004, 21(4): 451-453.
0 / / Recommend
Add to citation manager EndNote|Ris|BibTeX
URL: http://journal.ucas.ac.cn/EN/10.7523/j.issn.2095-6134.2004.4.004
http://journal.ucas.ac.cn/EN/Y2004/V21/I4/451
[ 1 ] 刘彦佩.图的可嵌入性理论.北京:科学出版社, 1994. [ 2 ] 刘彦佩.纵横嵌入术.北京:科学出版社,1994. [ 3 ] D Archdeacon, J Sirá nˇ.Characterizing planarity using theta graphs, J.Graph Theory, 1998, 27 :17 —20. [ 4 ] W X Xu.An efficient algorithm for planarity testing based on Wu-Liu' s crit erion.In:Proc 1-st China-USA Conf Graph Theory and itsAppli cations.Ann.N.Y.Acad.Sci., 1989, 576 :641 —652.