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.