Planar Decompositions and the Crossing Number of Graphs with an Excluded Minor

Wood, David R. and Telle, Jan Arne (2007) Planar Decompositions and the Crossing Number of Graphs with an Excluded Minor. In: Graph Drawing 14th International Symposium, GD 2006, September 18-20, 2006, Karlsruhe, Germany , pp. 150-161 (Official URL: http://dx.doi.org/10.1007/978-3-540-70904-6_16).

Full text not available from this repository.

Abstract

Tree decompositions of graphs are of fundamental importance in structural and algorithmic graph theory. Planar decompositions generalise tree decompositions by allowing an arbitrary planar graph to index the decomposition. We prove that every graph that excludes a fixed graph as a minor has a planar decomposition with bounded width and a linear number of bags. The crossing number of a graph is the minimum number of crossings in a drawing of the graph in the plane. We prove that planar decompositions are intimately related to the crossing number, in the sense that a graph with bounded degree has linear crossing number if and only if it has a planar decomposition with bounded width and linear order. It follows from the above result about planar decompositions that every graph with bounded degree and an excluded minor has linear crossing number. Analogous results are proved for the convex and rectilinear crossing numbers. In particular, every graph with bounded degree and bounded tree-width has linear convex crossing number, and every K_3,3-minor-free graph with bounded degree has linear rectilinear crossing number.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-70904-6_16
Classifications:G Algorithms and Complexity > G.420 Crossings
M Methods > M.999 Others
Z Theory > Z.999 Others
ID Code:770

Repository Staff Only: item control page

References

Therese Biedl, Erik D. Demaine, Christian A. Duncan, Rudolf Fleischer, and Stephen G. Kobourov. Tight bounds on maximal and maximum matchings. Discrete Math., 285(1-3):7-15, 2004.

Daniel Bienstock and Nathaniel Dean. Bounds for rectilinear crossing numbers. J. Graph Theory, 17(3):333-348, 1993.

Drago Bokal, Gasper Fijavz, and Bojan Mohar. The minor crossing number. SIAM J. Discrete Math., 20(2):344-356, 2006.

Eva Czabarka, Ondrej Sykora, Laszlo A. Szekely, and Imrich Vrto. Outerplanar crossing numbers, the circular arrangement problem and isoperimetric functions. Electron. J. Combin., 11(1):R81, 2004.

Reinhard Diestel. Graph theory, vol. 173 of Graduate Texts in Mathematics. Springer, 2nd edn., 2000.

Reinhard Diestel and Daniela Kühn. Graph minor hierarchies. Discrete Appl. Math., 145(2):167-182, 2005.

Hristo N. Djidjev and Imrich Vrto. Planar crossing numbers of genus g graphs. In Proc. 33rd International Colloquium on Automata, Languages and Programming (ICALP '06), vol. 4051 of Lecture Notes in Comput. Sci., pp. 419-430. Springer, 2006.

Enrique Garcia-Moreno and Gelasio Salazar. Bounding the crossing number of a graph in terms of the crossing number of a minor with small maximum degree. J. Graph Theory, 36(3):168-173, 2001.

Jesus Leanos and Gelasio Salazar. On the additivity of crossing numbers of graphs, 2006. http://www.ifisica.uaslp.mx/~gsalazar/RESEARCH/additivity.pdf.

Bojan Mohar and Carsten Thomassen. Graphs on surfaces. Johns Hopkins University Press, Baltimore, U.S.A., 2001.

Janos Pach and Geza Toth. Crossing number of toroidal graphs. Proc. 13th International Symp. on Graph Drawing (GD '05), vol. 3843 of Lecture Notes in Comput. Sci., pp. 334-342. Springer, 2006.

R. Bruce Richter and Jozef Siran. The crossing number of K3,n in a surface. J. Graph Theory, 21(1):51-54, 1996.

Neil Robertson and Paul D. Seymour. Graph minors. XVI. Excluding a non-planar graph. J. Combin. Theory Ser. B, 89(1):43-76, 2003.

Edward R. Scheinerman and Herbert S. Wilf. The rectilinear crossing number of a complete graph and Sylvester's "four point problem" of geometric probability. Amer. Math. Monthly, 101(10):939-943, 1994.

Farhad Shahrokhi, Ondrej Sykora, Laszlo A. Szekely, and Imrich Vrto. The gap between crossing numbers and convex crossing numbers. Towards a Theory of Geometric Graphs, vol. 342 of Contemporary Mathematics, pp. 249-258. Amer. Math. Soc., 2004.

Laszlo A. Szekely. A successful concept for measuring non-planarity of graphs: the crossing number. Discrete Math., 276(1-3):331-352, 2004.

David R. Wood and Jan Arne Telle. Planar decompositions and the crossing number of graphs with an excluded minor. 2006. http://www.arxiv.org/math/0604467.