Upper bounds for embedded or minor-excluding graphs

• K.J. Böröczky; J. Pach; G. Tóth: Planar crossing numbers of graphs embeddable in another surface. International Journal of Foundations of Computer Science, 17 (2006), 1005-1017.
  

Abstract. Let G be a graph of n vertices with maximum degree D that can be drawn without crossing in a closed surface of Euler characteristic chi. It is proved that then G can be drawn in the plane with at most c_chi*D*n crossings, where c_chi is a constant depending only on the surface. This result, which is tight up to a constant factor, is strengthened and generalized to the case when there is no restriction on the degrees of the vertices.

• Hristo Djidjev, Imrich Vrto: Planar Crossing Numbers of Genus g Graphs. ICALP (1) 2006: 419-430.

Abstract. Pach and Tóth [14] proved that any n-vertex graph of genus g and maximum degree d has a planar crossing number at most c^gdn, for a constant c > 1. We improve on this results by decreasing the bound to O(dgn), if g = o(n), and to O(g²), otherwise, and also prove that our result is tight within a constant factor.

• David R. Wood, Jan Arne Telle: Planar Decompositions and the Crossing Number of Graphs with an Excluded Minor. Graph Drawing 2006: 150-161

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.