CAREER: Geometric Techniques for Topological Graph Algorithms

经典的图算法设计技术不假定输入图的结构，因此受到人工实例的最坏情况保证的影响。在物流与规划、超大规模集成(VLSI)设计、图像处理和机器人导航等实际应用中，图形往往具有良好的拓扑结构：它们可以在平面上画出没有(或有几个)边交叉。这些结构可以被利用来获得算法优势吗？对这个问题的研究已经产生了强大的算法技术。然而，在过去的二十年里，算法设计者已经将这些技术发挥到了极限。这个项目旨在开发一种受几何学启发的新技术，可以克服现有技术的局限性。其核心思想是研究拓扑图的最短路径距离诱导的度量空间，并将离散几何的算法思想转化为求解问题。除了对实际应用的潜在影响外，该项目还概述了培训研究生和本科生的具体计划；该项目的实际方面将特别吸引来自不同背景的学生。该项目还计划传播最先进的拓扑图算法设计技术。这个项目将集中在两个具体的研究推动力上。首先研究用于设计近似算法的图嵌入。这一方向的灵感来自于通用指标嵌入技术的成功。其目的是通过考虑拓扑学来发展传统度量嵌入的新松弛，特别是专注于设计近似算法。第二个推论涉及拓扑图的不同几何结构。开发新的几何结构导致了拓扑图算法最近的突破。该项目提出了对几何结构的深入调查，包括受几何学研究启发的各种类型的分解和维度。这两种推力相辅相成：理解这些结构可以深入了解构建嵌入所需的条件，反之亦然。该项目还包括一些可以通过几何技术解决的算法问题，传统技术无法解决这些问题。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

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 from different backgrounds. 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.