Existence of Polyhedral Embeddings of Graphs |
| |
Authors: | Bojan Mohar |
| |
Institution: | (1) Department of Mathematics, University of Ljubljana; 1111 Ljubljana, Slovenia; E-mail: bojan.mohar@uni-lj.si, SI |
| |
Abstract: | It is proved that the decision problem about the existence of an embedding of face-width 3 of a given graph is NP-complete. A similar result is proved for some related decision problems. This solves a problem raised by Neil Robertson.
Received July 6, 1998
RID="*"
ID="*" Supported in part by the Ministry of Science and Technology of Slovenia, Research Project J1–0502–0101–98. |
| |
Keywords: | AMS Subject Classification (2000) Classes: 05C10 68Q17 |
本文献已被 SpringerLink 等数据库收录! |