CAREER: Geometric Techniques for Topological Graph Algorithms

University Of Massachusetts Amherst, Amherst MA

Investigators

Abstract

Classical techniques for designing graph algorithms do not assume structures of input graphs and therefore suffer from worst-case guarantees by artificial instances. Graphs arising in practical applications, including logistics and planning, very large-scale integration (VLSI) design, image processing, and robot navigation, often have nice topological structures: they can be drawn on the plane without (or with a few) edge crossings. Can these structures be exploited for algorithmic advantage? Research on this question has produced powerful algorithmic techniques. Nevertheless, algorithm designers have exploited these techniques to their limits over the past two decades. This project aims to develop a new class of techniques inspired by geometry counterparts that could overcome the limitations of the existing ones. The central idea is to study the metric space induced by shortest path distances of topological graphs and translate algorithmic ideas from discrete geometry to solve problems. In addition to potential impacts on practical applications, this project outlines specific plans to train students at both graduate and undergraduate levels; the practical aspects of this project would particularly be appealing to students. The project also plans to disseminate state-of-the-art algorithm design techniques for topological graphs. This project will focus on two specific research thrusts. The first studies graph embeddings for designing approximation algorithms. This direction is inspired by the success of embedding techniques for general metrics. The goal is to develop new relaxations of the traditional metric embedding by taking topology into account, specifically focusing on designing approximation algorithms. The second thrust concerns different geometric structures of topological graphs. Developing new geometric structures has resulted in recent breakthroughs in topological graph algorithms. The project proposes an in-depth investigation of geometric structures, including various types of decompositions and dimensions inspired by those studied in geometry. Both thrusts complement each other well: understanding these structures gives insights into what it takes to construct the embeddings and vice versa. This project also includes a number of algorithmic problems that can be settled by geometric techniques for which the traditional techniques fail. 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.