AF: Small: Graph Theory and Its Uses in Algorithms and Beyond

本项目致力于研究图的结构，以及利用对图结构的见解来设计更好的算法来解决基本的图问题，并证明这些算法的存在的否定结果。图是计算机科学、数学和其他学科中广泛应用的核心组合对象，无论在理论上还是在应用中都是如此。图形是各种类型网络的自然模型，包括计算机和交通网络。此外，图还用于表示各种对象之间的数据和关系。这个项目的目标之一是研究复杂图的性质，以便设计更快、更准确的图算法。此外，该项目将专注于几个基本的图问题，这些问题与随时间发展的网络中的路由流量有关，以及计算图的布局，目标是创建良好的可视化。它还将探索使用图论技术来证明否定结果，表明为几个中心图问题设计快速而准确的算法是不可能的。更具体地说，该项目由三个主要部分组成。第一部分集中在图论问题上，旨在更好地理解复杂图的结构。这些问题包括获得著名的排除格定理的更强的界，设计在具有较少交点的平面上绘制图的良好算法，以及研究图论问题研究中产生的一个新的图划分问题。第二部分重点研究最短路径问题的动态算法：给定一个经过边删除和插入的图，目标是对顶点对之间的最短路径查询提供快速而准确的响应。这类问题既出现在实际场景中(例如用于路由流量的应用)，也出现在理论环境中(动态最短路径算法已被用作解决许多中心理论问题的子程序)。这一部分的目标是获得对查询提供高精度响应的非常快速的算法。在第三部分中，该项目将专注于几个被认为很难逼近的密切相关的问题，并将试图通过利用图论技术来证明这一点。该项目的这一部分与近似和概率可核查证明的困难领域密切相关，其目标之一是增加这些领域和算法图理论之间的思想和技术流动。这一奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

This project focuses on studying structure of graphs, as well as using insights about graph structure in order to design better algorithms for basic graph problems, and to prove negative results about the existence of such algorithms. Graphs are central combinatorial objects that are widely used in Computer Science, Mathematics, and other disciplines, both in theory and in applications. Graphs are a natural model of various types of networks, including computer and traffic networks. Additionally, graphs are also used to represent data and relationships between various objects. One of the goals of this project is to study properties of complex graphs that can be exploited in order to design faster and more accurate graph algorithms. In addition, the project will focus on several fundamental graph problems that have connections to routing traffic in a network that evolves over time, and to computing a layout of a graph with the goal of creating a good visualization of it. It will also explore the use of graph-theoretic techniques in proving negative results that show that designing fast and accurate algorithms for several central graph problems is impossible.More specifically, the project consists of three main parts. The first part focuses on graph-theoretic questions that aim at better understanding the structure of complex graphs. The questions include obtaining stronger bounds on the famous Excluded Grid Theorem, designing good algorithms for drawing graphs in the plane with few crossings, and studying a new problem on graph partitioning that arose from the study of graph theoretic questions. The second part focuses on dynamic algorithms for shortest-paths problems: given a graph that undergoes edge deletions and insertions, the goal is to provide quick and accurate responses to shortest-paths queries between pairs of vertices. This type of questions arises both in practical scenarios (such as applications for routing traffic), and in theoretical settings (algorithms for dynamic shortest-paths have been used as sub-routines in solving many central theoretical problems). The goal of this part is to obtain very fast algorithms that provide high-precision responses to the queries. In the third part, the project will focus on several closely related problems that are believed to be hard to approximate, and will attempt to prove that this is indeed the case, by exploiting graph-theoretic techniques. This part of the project is closely related to the areas of Hardness of Approximation and Probabilistically Checkable Proof, and one of its goals is to increase the flow of ideas and techniques between these areas and Algorithmic Graph Theory.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.