The crossing number of a graph is the minimum number of crossings in a drawing of the graph in the plane. Our main result is that every graph G that does not contain a fixed graph as a minor has crossing number O(Δ), where G has n vertices and maximum degree Δ. This dependence on n and Δutri; is best possible. This result answers an open question of Wood and Telle [New York J. Mathematics, 2007], who proved the best previous bound of O(Δ2n). In addition, we prove that every K5-minor- free graph G has crossing number at most 2 ∑u deg(u)2, which again is the best possible dependence on the degrees of G. We also study the convex and rectilinear crossing numbers, and prove an O(Δn)bound for the convex crossing number of bounded pathwidth graphs, and a ∑ur bound for the rectilinear crossing number of K3,3-minor-free graphs. Copyright 2008 ACM.

, , , , , , ,
24th Annual Symposium on Computational Geometry, SCG'08
School of Computer Science

Dujmović, V, Kawarabayashi, K.-I. (Ken-Ichi), Mohar, B. (Bojan), & Wood, D. (2008). Improved upper bounds on the crossing number. Presented at the 24th Annual Symposium on Computational Geometry, SCG'08. doi:10.1145/1377676.1377739