Rectilinear Crossing Number of Graphs Excluding a Single-Crossing Graph as a Minor

Abstract

The crossing number of a graph 𝐺 is the minimum number of crossings in any drawing of 𝐺 in the plane. The rectilinear crossing number of 𝐺 is the minimum number of crossings in any straight-line drawing of 𝐺. The Fáry-Wagner theorem states that planar graphs have rectilinear crossing number zero. By Wagner’s theorem, that is equivalent to stating that every graph that excludes 𝐾₅ and 𝐾₃,₃ as minors has rectilinear crossing number 0. We are interested in discovering other proper minor-closed families of graphs which admit strong upper bounds on their rectilinear crossing numbers. Unfortunately, it is known that the crossing number of 𝐾₃,ₙ with 𝑛 ≥ 1, which excludes 𝐾₅ as a minor, is quadratic in 𝑛, more specifically Ω(𝑛²). Since every 𝑛-vertex graph in a proper minor closed family has O(𝑛) edges, the rectilinear crossing number of all such graphs is trivially O(𝑛²). In fact, it is not hard to argue that O(𝑛) bound on the crossing number is the best one can hope for general enough proper minor-closed families of graphs and that to achieve O(𝑛) bounds, one has to both exclude a minor and bound the maximum degree of the graphs in the family. In this thesis, we do that for bounded degree graphs that exclude a single-crossing graph as a minor. A single-crossing graph is a graph whose crossing number is at most one. The main result of this thesis states that every graph 𝐺 that does not contain a single-crossing graph as a minor has a rectilinear crossing number O(∆𝑛), where 𝐺 has 𝑛 vertices and maximum degree ∆. This dependence on 𝑛 and ∆ is best possible. Note that each planar graph is a single-crossing graph, as is the complete graph 𝐾₅ and the complete bipartite graph 𝐾₃,₃. Thus, the result applies to 𝐾₅-minor-free graphs, 𝐾₃,₃-minor free graphs, as well as to bounded treewidth graphs. In the case of bounded treewidth graphs, the result improves on the previous best known bound of O(∆² · 𝑛) by Wood and Telle [New York Journal of Mathematics, 2007]. In the case of 𝐾₃,₃-minor free graphs, our result generalizes the result of Dujmovic, Kawarabayashi, Mohar and Wood [SCG 2008].