Existence of polyhedral embeddings of graphs

Authors
Mohar, B
Citation
B. Mohar, Existence of polyhedral embeddings of graphs, COMBINATORI, 21(3), 2001, pp. 395-401
Citations number
10
Categorie Soggetti
Mathematics,"Computer Science & Engineering
Journal title
COMBINATORICA
ISSN journal
02099683 → ACNP
Volume
21
Issue
3
Year of publication
2001
Pages
395 - 401
Database
ISI
SICI code
0209-9683(2001)21:3<395:EOPEOG>2.0.ZU;2-U
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 R obertson.