Minimal Obstructions for 1Immersions and Hardness of 1Planarity TestingKorzhik, Vladimir P. and Mohar, Bojan (2009) Minimal Obstructions for 1Immersions and Hardness of 1Planarity Testing. In: Graph Drawing 16th International Symposium, GD 2008, September 21 24, 2008 , pp. 302312(Official URL: http://dx.doi.org/10.1007/9783642002199_29). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783642002199_29
AbstractA graph is 1planar if it can be drawn on the plane so that each edge is crossed by no more than one other edge. A non1planar graph G is minimal if the graph G − e is 1planar for every edge e of G. We construct two inﬁnite families of minimal non1planar graphs and show that for every integer n ≥ 63, n 54 there are at least 2 4 − 4 nonisomorphic minimal non1planar graphs of order n. It is also proved that testing 1planarity is NPcomplete. As an interesting consequence we obtain a new, geometric proof of NPcompleteness of the crossing number problem, even when restricted to cubic graphs. This resolves a question of Hlineny.
Actions (login required)
