Topological graph theory studies how graphs can be drawn on surfaces in different ways. One of its fundamental problems is to determine for each surface S the set F of minimal graphs that have a cross no matter how they are drawn on S. It follows from the celebrated result of Robertson and Seymour on Wagner?s conjecture that F is finite for every surface S. However, nothing is known about the elements of F, except when S is the sphere or the projective plane. Over the past twenty years, many attempts were made by many researchers yet no new F is completely determined. The PI proposes a different approach to this problem. Results generated from this proposal could lead to a characterization of core members of each F, which would essentially determine F since other members of F are sporadic unimportant graphs.
The goal of this project is to understand the behavior of topological graph parameters such as genus and crossing number when the graph is well connected and is big. To achieve this goal, it will be necessary to study the interactions between connectivity, genus, and the size of the graph. A good understanding of such interactions would bring significant insights to the entire topological graph theory. Since surface graphs are so fundamental, these results could have very strong theoretical (on graph structures) and practical (on graph algorithms) impact in many areas of graph theory.
The goal of this project is to understand the behavior of topological graph parameters when the graph is well connected and is big. To achieve this goal, it will be necessary to study the interactions between connectivity, genus, crossing number, and the size of the graph. In particular, the PI proposed to study projective planar graphs, large nonplanar graphs, and the crossing number of graphs. He has made significant progress in all directions. The set of forbidden minors for projective planar graphs consists of 35 graphs, as shown by Archdeacon. This set is not very satisfactory in the sense that most of its members have connectivity only three or less. Since in many applications, graphs in consideration have connectivity higher than three, a certificate of comparable connectivity would be desirable. Jointly with his student Perry Iverson, the PI successfully determined all 23 forbidden minors for internally 4-connected projective planar graphs. What this means is that each internally 4-connected non-projective planar graph can be certified by one of our 23 internally 4-connected forbidden minors. The increase in connectivity makes our set much more useful then the set of 35. It is worth pointing out that methods developed in solving this problem is very general and can be applied to other similar problems. To understand graphs of high genus, a good starting point is the set of minimal non-planar graphs. Similarly, since we are interested in large graphs, it is desirable to know the set of unavoidable large non-planar graphs. This problem is easy if there is no requirement on connectivity. However, the situation is different for well-connected graphs. Jointly with Bogdan Oporowski, Robin Thomas, and Dirk Vertigan, the PI solved this problem for internally 4-connected graphs. That is, they determined all the unavoidable large internally 4-connectd non-planar graphs. In the same paper, this result is used to establish the following result on crossing number: for every positive integer k, there are only finitely many 3-connected 2-crossing-critical graphs that do not contain the Mobius ladder of length k. This result suggests that a complete characterization of 2-crossing-critical graphs is possible. Another fundamental problem in dealing with well-connected large graphs is to determine, for each positive integer k, all the unavoidable k-connected large graphs. This problem is solved for k less than or equal to four, but is still open for all other k. Jointly with Carolyn Chun, the PI determined, for each positive integer k, all the unavoidable loosely-k-connected (which is a slight modification of the ordinary k-connectivity) infinite graphs. Very recently, a finite-graph version of this result is announced by Jim Geelen and Benson Joeris. This project has several broader impacts. The PI offered several courses on related topics, which include many results from this project. At least seven graduate students (including three female students) participated in different aspects of this project under the supervision of the PI. Two of these students received their PhD degrees recently. The PI also mentored the combinatorics group of Louisiana Tech University, which is a non-PhD-granting institution. At least one student from this program received his MS degree for working on problems related to this project.
