STRONG EMBEDDINGS OF PLANAR GRAPHS ON HIGHER SURFACES  

作　　者：刘同印 刘彦佩 

出　　处：《Acta Mathematica Scientia》2002年第4期542-548,共7页数学物理学报（B辑英文版）

基　　金：Supported by NNSFC(69973001)

摘　　要：In this paper, the authors discuss the upper bound for the genus of strong embeddings for 3-connected planar graphs on higher surfaces. It is shown that the problem of determining the upper bound for the strong embedding of 3-connected planar near-triangulations on higher non-orientable surfaces is NP-hard. As a corollary, a theorem of Richter, Seymour and Siran about the strong embedding of 3-connected planar graphs is generalized to orientable surface.In this paper, the authors discuss the upper bound for the genus of strong embeddings for 3-connected planar graphs on higher surfaces. It is shown that the problem of determining the upper bound for the strong embedding of 3-connected planar near-triangulations on higher non-orientable surfaces is NP-hard. As a corollary, a theorem of Richter, Seymour and Siran about the strong embedding of 3-connected planar graphs is generalized to orientable surface.

关 键 词：surface NP-HARD circuit double cover strong embedding 

分 类 号：O157.5[理学—数学]