Tight Upper Bounds on the Crossing Number in a Minor-Closed Class
share
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(Δ n), where G has n vertices and maximum degree Δ. This dependence on n and Δ 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(Δ^2 n). 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 ∑_v(v)^2 bound for the rectilinear crossing number of K_3,3-minor-free graphs.
READ FULL TEXT