CAREER: Exploiting Topology in Graph Algorithm Design

About This Grant

Graphs, also known as networks, are used to represent many kinds of relationships between pairs of entities. For example, a graph may describe pairs of networking devices directly connected together or pairs of roadway intersections connected by a stretch of road. Many useful tasks, such as understanding the reliability of a computer network or finding the fastest route between two locations, can be performed by doing computations on these graphs. When a graph has certain properties such as being drawable on a piece of paper without crossings between its connections, it becomes possible to do these types of computations much more quickly than if the properties were not present. Many of these faster computations rely on important results from topology, the mathematical study of what properties geometric objects maintain after certain types of deformations. This project seeks to better understand the role topology can take both in performing fast computations on graphs and explaining what graph properties are necessary for these fast computations. The project aims to make substantial topology based additions to the toolkit used in graph computations. These additions should make new computational tasks possible and greatly simplify established tasks. The project involves a substantial education component as well that includes educating students on the known connections between topology and computer science and providing undergraduate minority students their first opportunities to participate in the research process. The research activities have three components. The first involves generalizing known planar graph algorithms for many fundamental problems in computer science to graphs embeddable in low complexity surfaces. The second component explores how topological intuitions and tools created during the first component can be used to solve difficult problems back in the setting of planar graphs. The third component involves pushing these tools to their limits in the creation of algorithms for more general families of graphs than those embeddable in low complexity surfaces with a focus on the so-called H-minor-free graphs. The types of problems studied for all three components include the computations of optimal network flows, minimum cuts, and shortest paths. Student education will take place through the development of a new course in computational topology at the awardee institution that focusses on graph algorithms and topological data analysis. Activities for undergraduate minority students will consist primarily of the implementation and experimental analysis of algorithms designed during the primary research activities. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.