On graph crossing number

Abstract

This thesis explores the theory of crossing numbers, a significant area in graph theory focused on minimizing the number of edge crossings in graph drawings. This field, originating from Turán’s Brick Factory problem, has expanded significantly over the past five decades. We present original results on the crossing numbers of several graph families, namely, generalized Petersen graphs, circulant graphs, and the Cartesian product of graphs. In the first chapter we give an introduction to crossing numbers. The theory of crossing numbers has evolved since Turán’s Brick Factory problem, which sought the crossing number of a complete bipartite graph. This chapter outlines the current state of research. We highlight that while exact crossing numbers have been determined for some graph families, many others remain unsolved, often with only conjectured bounds. In Chapter 2, we present our initial results which focus on generalized Petersen graphs. We prove two conjectures by Zhou and Wang (2008) regarding the crossing numbers of two subfamilies of generalized Petersen graphs. Additionally, we develop a method using Watkins’ results to efficiently determine if two generalized Petersen graphs with different parameters are isomorphic. In Chapter 3, we examine the planar crossing number of circulant graphs. We confirm a previously proposed conjecture by Wang and Huang (2008). Additionally, we determine the crossing number for a range of other circulant graphs and initiate the study of a subfamily of circulant graphs that has not been previously investigated. Chapter 4 extends our investigation to the projective plane. The majority of the work that has been done involves the drawing of graphs on the sphere (or equivalently the plane), but few results are known for the crossing number of graphs drawn on other surfaces. Building on the work of Ho (2012) and Cheon (2020), we determine the projective plane crossing numbers for a further subfamily of quartic circulant graphs, and propose a conjecture. In Chapter 5, we obtain the crossing number of the Cartesian product S3□Pn of the star S3 and the path Pn on an infinite number of surfaces. To our knowledge, there is only one other infinite family of graphs for which the crossing number has been determined on every orientable and nonorientable surface, namely the complete bipartite graph K3,n. Our result thus means that we now have the second infinite family of graphs for which the crossing number has been completely determined for any orientable surface and for nonorientable surfaces of sufficiently large Euler genus. This thesis makes significant contributions to the understanding of the crossing number of various graph families on different surfaces. We provide both theoretical advancements and conjectures, offering a foundation for future research in this domain.