数学物理学报(英文版) ›› 2002, Vol. 22 ›› Issue (4): 542-548.

• 论文 • 上一篇    下一篇

STRONG EMBEDDINGS OF PLANAR GRAPHS ON HIGHER SURFACES

 刘同印, 刘彦佩   

  1. Department of Mathematics, Northern Jiaotong University, Beijing 100044, China
  • 出版日期:2002-10-14 发布日期:2002-10-14
  • 基金资助:

    Supported by NNSFC (69973001)

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)

摘要:

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.

关键词: Surface, NP-hard, circuit double cover, strong embedding

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

中图分类号: 

  • 05C10