| STRONG EMBEDDINGS OF PLANAR GRAPHS ON HIGHER SURFACES |
| |
| 引用本文： | 刘同印,刘彦佩. STRONG EMBEDDINGS OF PLANAR GRAPHS ON HIGHER SURFACES[J]. 数学物理学报(B辑英文版), 2002, 22(4) |
| |
| 作者姓名： | 刘同印 刘彦佩 |
| |
| 作者单位： | Liu Tongyin Liu YanpeiDepartment of Mathematics，Northern Jiaotong University，Beijing 100044，China |
| |
| 基金项目： | 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.
|
STRONG EMBEDDINGS OF PLANAR GRAPHS ON HIGHER SURFACES |
| |
| Liu Tongyin Liu Yanpei. STRONG EMBEDDINGS OF PLANAR GRAPHS ON HIGHER SURFACES[J]. Acta Mathematica Scientia, 2002, 22(4) |
| |
| Authors: | Liu Tongyin Liu Yanpei |
| |
| Affiliation: | Liu Tongyin Liu YanpeiDepartment of Mathematics,Northern Jiaotong University,Beijing 100044,China |
| |
| 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 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. |
| |
| Keywords: | Surface NP-hard circuit double cover strong embedding |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
