Return to search

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

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].

Identiferoai:union.ndltd.org:uottawa.ca/oai:ruor.uottawa.ca:10393/44823
Date19 April 2023
CreatorsLa Rose, Camille
ContributorsDujmovic, Vida
PublisherUniversitΓ© d'Ottawa / University of Ottawa
Source SetsUniversitΓ© d’Ottawa
LanguageEnglish
Detected LanguageEnglish
TypeThesis
Formatapplication/pdf
RightsAttribution-ShareAlike 4.0 International, http://creativecommons.org/licenses/by-sa/4.0/

Page generated in 0.0023 seconds