UT Dallas Computer Science Colloquium Series Presents
UT Dallas Professor of Computer Science
“Surface Embedded Graphs, Shortest Homology Bases, and Holiest Paths”
Several problems from graphics and other application areas ask for a surface to be cut into less complicated pieces. One method of finding good cuts is to solve some discrete optimization problem on an edge-weighted graph embedded in the surface. These algorithms are often made more simple if we assume the shortest path between any two vertices is unique.
For this talk, Dr. Fox will begin by discussing a new algorithm for one such optimization problem, that of computing minimum length homology bases. Given a graph of n vertices embedded on a surface of genus g (with g holes), the problem asks for a set of 2g cycles of minimum total length that describe all the ways one can walk around features of the surface. The algorithm runs in O(g^3 n log n) time assuming shortest paths are unique.
Unfortunately, modifying such algorithms to work without uniqueness of shortest paths has traditionally required adding randomness to otherwise deterministic algorithms or the use of complicated tie-breaking schemes. For the second half of the talk, he will present a simple and deterministic method of perturbing edge lengths so that shortest paths become unique. Algorithms can be modified to work with these unique homologically lexicographic least leftmost (or holiest) paths with only an O(g) factor increase in running time. Dr. Fox will conclude by discussing additional consequences of this work including new linear time algorithms for many discrete optimization problems on unweighted surface embedded graphs.
This talk features joint work with Glencora Borradaile, Erin Wolf Chambers, Jeff Erickson, Amir Nayyeri, and Luvsandondov Lkhamsuren.
Dr. Kyle Fox joined the University of Texas at Dallas in Fall 2017 as an Assistant Professor after completing a postdoc at Duke University. He obtained his Ph.D. from the University of Illinois at Urbana-Champaign in 2013. His research interests are primarily in algorithms, including computational geometry and topology, combinatorial optimization, and their applications to data analysis and graph algorithms. He has published in top theory and computational geometry conferences including STOC, SODA, and SoCG. He was a recipient of the Department of Energy Office of Science Graduate Fellowship and a winner of the C. W. Gear Outstanding Graduate Student award while at the University of Illinois.
Refreshments will be served at 9:45am.