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

A family of graphs is said to have linear crossing number, if there is constant \(c\) such that \(cr(G)\leq c | V(G)| \). \textit{J. Pach} and \textit{G. Tóth} [Lect. Notes Comput. Sci. 3843, 334--342 (2006; Zbl 1171.05326)] proved that graphs of bounded genus and bounded degree have linear crossing number. The main result of the paper under review is that graphs that do not have a fixed minor but have bounded maximum degree have linear crossing number. The main tool of the paper is generalization of the tree decomposition, called planar decomposition, which is intimately connected to crossing numbers. The theorem mentioned above follows from the result that every graph that avoids a fixed graph as minor has a planar decomposition with bounded width and a linear number of bags. It is shown 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. Analogous results are shown for the convex and rectilinear crossing numbers. In particular, every graph with bounded degree and bounded treewidth has linear convex crossing number, and every \(K_{3,3}\)-minor-free graph with bounded degree has linear rectilinear crossing number.