This project will study three broad families of optimization problems: graph routing, graph drawing, and vertex sparsification. Graph routing problems typically aim at connecting pairs of graph vertices with disjoint or nearly disjoint paths. Routing problems are central to combinatorial optimization, and arise in many different applications. Algorithms for graph drawing assist with visualizing a given graph, by appropriately drawing it in the plane. Graph sparsifiers allow us to replace a given graph by a much smaller one, that preserves the routing properties of the original graph. Optimization problems can then be solved on the smaller graph, thus obtaining faster algorithms. This project aims at developing better approximation algorithms for graph routing and drawing problems, and constructing better and smaller vertex sparsifiers. The PI will also study graph partitioning problems, that play a central role in designing algorithms for many problems in the areas of graph routing, drawing, sparsification, and beyond.
Graphs are among the most basic combinatorial objects, and are often used to model various applications, or to represent data. Algorithms for graph partitioning, routing and drawing are central tools for manipulating graphs and solving optimization problems on them. Designing better approximation algorithms for such problems will require developing new algorithmic paradigms, that will most likely find other uses across the field of approximation algorithms and beyond. The problems the PI studies have interesting connections to other areas, including Graph Minor Theory, Fixed Parameter Tractability, and VLSI Design. This project presents an opportunity for collaboration with these areas, with the goal of combining their diverse technical tools and insights. This research offers a broad range of opportunities for student projects, and will involve graduate students from TTIC and University of Chicago, as well as students from other institutions who participate in TTIC's summer internship program. The PI will also participate in activities aimed at encouraging a broader involvement of women in theoretical computer science, including participation in workshops and mentorship programs whose target audience is undergraduate and graduate female students.
