RUI: Crossing numbers for topological drawings of the complete graph, rotation schemes, and interior triple systems.

This award supports the Principal Investigator's research in Mathematics with a focus on the study of crossing numbers. Crossing numbers date back to World War II, when the mathematician Paul Turán worked on a labor camp moving carts filled with bricks from kilns to storage places using a railway system. In his own words ''...the work itself was not difficult; the trouble was only at the crossings. The trucks generally jumped the rails there, and the bricks fell out of them; in short this caused a lot of trouble and loss of time which was rather precious to all of us..."" He realized that the situation could be improved by a railway system with the smallest number of crossings. The general problem with an arbitrary number of kilns and storage places turned out to be extremely difficult and has not been solved to date. A generalized abstraction of this problem is to consider drawings where some points are to be connected by curves and the goal is to minimize the number of crossings. Crossing numbers are important to everyday life and technology. Drawings of graphs are a helpful tool to visually represent connections and interrelations among objects or subjects, such as maps, genealogy tress, or organizational charts. To ease the understanding of such information, drawings with few crossings are highly desirable. Crossing numbers are also important to the development of electronic circuits, such as computer processors, whose components must be connected by non crossing electrical links in order to avoid short circuits. The accessible nature of related problem statements and their important applications make this project suitable to the direct involvement of graduate and undergraduate students.

Minimizing the number of crossings in a drawing of a graph in the plane is a major problem in topological and geometric graph theory. Crossing numbers of the complete graph are particularly important because, using random embeddings, bounds on the crossing number of the complete graph imply bounds on the crossing number of arbitrary graphs. Separation of points by a straight line (halving lines, k-edges, k-sets) has extensively been used to understand the complexity of finite sets of points in the plane. The PI and coauthors recently developed a separation concept for topological drawings of the complete graph in the plane. They used this concept to settle a long standing crossing number conjecture for several families of drawings. The goal of this project is to use this separation concept as a new approach to the Harary-Hill conjecture on the topological crossing number of the complete graph and its variations to other topological settings. Being able to separate points in topological graph drawings opens up a world of possibilities; problems involving k-edges, halving lines, and convexity will be studied for the first time on this topological framework. The project will significantly advance the understanding of the fundamental structure of topological drawings of graphs in the plane.