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, Heraklion, Crete, Greece , pp. 302-312 (Official URL: http://dx.doi.org/10.1007/978-3-642-00219-9_29).

Full text not available from this repository.

Abstract

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
ID Code:916

Repository Staff Only: item control page

References

Borodin, O.V.: Solution of Ringel’s problem about vertex bound colouring of planar graphs and colouring of 1-planar graphs [in Russian]. Metody Discret. Analiz. 41, 12–26 (1984)

Borodin, O.V.: A new proof of the 6-color theorem. J. Graph Theory 19, 507–521 (1995)

Borodin, O.V., Kostochka, A.V., Raspaud, A., Sopena, E.: Acyclic colouring of 1-planar graphs. Discrete Analysis and Operations Researcher 6, 20–35 (1999)

Chen, Z.-Z.: Approximation algorithms for independent sets in map graphs. Journal of Algorithms 41, 20–40 (2001)

Chen, Z.-Z.: New bounds on the number of edges in a k-map graph. Lecture Notes in Computer Science 3106,319–328, Springer, Heidelberg (2004)

Chen, Z.-Z., Kouno M.: A linear-time algorithm for 7-coloring 1-plane graphs. Algorithmica 43, 147–177 (2005)

Fabrici, I., Madaras, T.:The structure of 1-planar graphs. Discrete Math. 307, 854–865 (2007)

Garey, M.R., Johnson, D.S., Stockmeyer, L.: Some simplified NP-complete graph problems. Theor. Comp. Sci. 1, 237–267 (1976)

Hlineny, P.: Crossing number is hard for cubic graphs. J. Combin. Theory, Ser. B 96, 455– 471 (2006)

Korzhik, V.P.: Minimal non-1-planar graphs. Discrete Math. 308, 1319–1327 (2008)

Ringel, G.: Ein Sechsfarbenproblem auf der Kugel. Abh. Sem. Univ. Hamburg 29, 107–117 (1965)

Schumacher, H.: Zur Struktur 1-planarer Graphen. Math. Nachr. 125, 291–300 (1986)