Minimal Obstructions for 1-Immersions and Hardness of 1-Planarity Testing

DOI10.1007/978-3-642-00219-9_29zbMath1213.05055arXiv1110.4881MaRDI QIDQ3611864

Bojan Mohar, Vladimir P. Korzhik

Publication date: 3 March 2009

Published in: Journal of Graph Theory, Graph Drawing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1110.4881

zbMATH Keywords

topological graph; 1-planar graph; 1-immersion; crossing edges

Mathematics Subject Classification ID

05C10: Planar graphs; geometric and topological aspects of graph theory

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C62: Graph representations (geometric and intersection representations, etc.)