New York Journal of Mathematics
Volume 13 (2007) 117-146

  

David R. Wood and Jan Arne Telle

Planar decompositions and the crossing number of graphs with an excluded minor


Published: May 29, 2007
Keywords: Graph drawing, crossing number, rectilinear crossing number, convex crossing number, outerplanar crossing number, graph decomposition, planar decomposition, tree decomposition, tree-width, tree-partition, tree-partition-width, planar partition, graph minor
Subject: 05C62 (graph representations), 05C10 (topological graph theory), 05C83 (graph minors)

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 particular, 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 K3,3-minor-free graph with bounded degree has linear rectilinear crossing number.


Acknowledgements

The research of David Wood is supported by a Marie Curie Fellowship of the European Community under contract 023865, and by the projects MEC MTM2006-01267 and DURSI 2005SGR00692.


Author information

David R. Wood:
Departament de Matemática Aplicada II, Universitat Politècnica de Catalunya, Barcelona, Spain
david.wood@upc.es

Jan Arne Telle:
Department of Informatics, The University of Bergen, Bergen, Norway
Jan.Arne.Telle@ii.uib.no