Acta mathematica scientia,Series B ›› 2002, Vol. 22 ›› Issue (4): 542-548.

• Articles • Previous Articles     Next Articles

STRONG EMBEDDINGS OF PLANAR GRAPHS ON HIGHER SURFACES

 LIU Tong-Yin, LIU Yan-Pei   

  1. Department of Mathematics, Northern Jiaotong University, Beijing 100044, China
  • Online:2002-10-14 Published:2002-10-14
  • Supported by:

    Supported by NNSFC (69973001)

Abstract:

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 emedding of 3-connected planar neartriangulations 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.

Key words: Surface, NP-hard, circuit double cover, strong embedding

CLC Number: 

  • 05C10
Trendmd