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

Korzhik, Vladimir P. and Mohar, Bojan (2009) Minimal Obstructions for 1-Immersions and Hardness of 1-Planarity Testing. In: Graph Drawing 16th International Symposium, GD 2008, September 21- 24, 2008 , pp. 302-312(Official URL:

Full text not available from this repository.


A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by no more than one other edge. A non-1-planar graph G is minimal if the graph G − e is 1-planar for every edge e of G. We construct two infinite families of minimal non-1-planar graphs and show that for every integer n ≥ 63, n 54 there are at least 2 4 − 4 non-isomorphic minimal non-1-planar graphs of order n. It is also proved that testing 1-planarity is NP-complete. As an interesting consequence we obtain a new, geometric proof of NP-completeness of the crossing number problem, even when restricted to cubic graphs. This resolves a question of Hlineny.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-642-00219-9_29
Classifications: G Algorithms and Complexity > G.770 Planarity Testing

Actions (login required)

View Item View Item