Some problems in topological graph theory

Louisiana State University, Baton Rouge LA

Investigators

Abstract

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.