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 FaΜ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].
| Identifer | oai:union.ndltd.org:uottawa.ca/oai:ruor.uottawa.ca:10393/44823 |
| Date | 19 April 2023 |
| Creators | La Rose, Camille |
| Contributors | Dujmovic, Vida |
| Publisher | UniversitΓ© d'Ottawa / University of Ottawa |
| Source Sets | UniversitΓ© dβOttawa |
| Language | English |
| Detected Language | English |
| Type | Thesis |
| Format | application/pdf |
| Rights | Attribution-ShareAlike 4.0 International, http://creativecommons.org/licenses/by-sa/4.0/ |
Page generated in 0.0023 seconds