CAREER: Exploiting Topology in Graph Algorithm Design

图也称为网络，用于表示实体对之间的多种关系。例如，图可以描述直接连接在一起的成对网络设备或由一段道路连接的成对道路交叉口。许多有用的任务，如了解计算机网络的可靠性或寻找两个位置之间的最快路线，可以通过对这些图进行计算来执行。当图形具有某些属性时，例如可以在一张纸上绘制，其连接之间没有交叉点，就可以比没有这些属性的情况下更快地进行这些类型的计算。其中许多更快的计算依赖于拓扑学的重要结果，拓扑学是对几何对象在特定类型的变形后保持哪些属性的数学研究。这个项目试图更好地理解拓扑学在对图执行快速计算和解释这些快速计算需要哪些图属性方面可以扮演的角色。该项目旨在对图形计算中使用的工具包进行实质性的基于拓扑的添加。这些补充应该会使新的计算任务成为可能，并极大地简化已有的任务。该项目还包括一个重要的教育部分，包括教育学生了解拓扑学和计算机科学之间的已知联系，并为本科生提供参与研究过程的第一次机会。研究活动包括三个部分。第一个涉及将计算机科学中许多基本问题的已知平面图算法推广到可嵌入低复杂性表面的图。第二个组件探索如何使用在第一个组件中创建的拓扑直觉和工具来解决平面图形设置中的难题。第三个组成部分涉及将这些工具推向它们的极限，以创建比那些可嵌入低复杂性曲面的图族更一般的算法，重点是所谓的H-次要自由图。针对所有三个组成部分研究的问题类型包括最优网络流量、最小割数和最短路径的计算。学生教育将通过在获奖机构开发一门新的计算拓扑学课程来进行，该课程侧重于图形算法和拓扑数据分析。针对少数族裔本科生的活动将主要包括在主要研究活动期间设计的算法的实施和实验分析。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Graphs, also known as networks, are used to represent many kinds of relationships between pairs of entities. For example, a graph may describe pairs of networking devices directly connected together or pairs of roadway intersections connected by a stretch of road. Many useful tasks, such as understanding the reliability of a computer network or finding the fastest route between two locations, can be performed by doing computations on these graphs. When a graph has certain properties such as being drawable on a piece of paper without crossings between its connections, it becomes possible to do these types of computations much more quickly than if the properties were not present. Many of these faster computations rely on important results from topology, the mathematical study of what properties geometric objects maintain after certain types of deformations. This project seeks to better understand the role topology can take both in performing fast computations on graphs and explaining what graph properties are necessary for these fast computations. The project aims to make substantial topology based additions to the toolkit used in graph computations. These additions should make new computational tasks possible and greatly simplify established tasks. The project involves a substantial education component as well that includes educating students on the known connections between topology and computer science and providing undergraduate minority students their first opportunities to participate in the research process.The research activities have three components. The first involves generalizing known planar graph algorithms for many fundamental problems in computer science to graphs embeddable in low complexity surfaces. The second component explores how topological intuitions and tools created during the first component can be used to solve difficult problems back in the setting of planar graphs. The third component involves pushing these tools to their limits in the creation of algorithms for more general families of graphs than those embeddable in low complexity surfaces with a focus on the so-called H-minor-free graphs. The types of problems studied for all three components include the computations of optimal network flows, minimum cuts, and shortest paths. Student education will take place through the development of a new course in computational topology at the awardee institution that focusses on graph algorithms and topological data analysis. Activities for undergraduate minority students will consist primarily of the implementation and experimental analysis of algorithms designed during the primary research activities.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.