AF: Small: Collaborative Research: Efficient Algorithms for Cycles on Surfaces

许多计算问题都是从绘制在曲面上的网格或图形模型开始的。一个经典的例子是在计算机图形系统中使用的物理对象的表示，方法是在对象的表面上选择点，并用其角是所选点的三角形来逼近该表面：这些点成为节点，三角形的边成为图形的边，并且该图形可以被视为绘制在该对象的表面上。当曲面更简单时，在曲面上操作图形的算法就会更高效；当曲面具有手柄和洞等特征时，曲面就会更复杂。处理这些特征的一种常见方法是通过将曲面切开以移除手柄和孔来简化曲面。该项目将开发准确而有效的方法，以这种方式简化曲面以及其他密切相关的问题。由于这些问题是根本性的，针对它们的新算法将为广泛的应用提供有效的预处理工具。PIs将让研究生参与研究，并在早期成功的基础上，培养一个友好的研究环境，努力从代表不足的人群中招收学生。这个项目将解决上述的“割图”问题，以及寻找最小圈基(一种表示图中所有圈的最小成本方式)和最小同调基数(一种表示图形表面上所有句柄和洞的最小成本方式)的问题。对于曲面上的图，这些问题是非常密切相关的。通过将这些问题放在一起考虑，PI将开发出可转换为这些类型图表中的其他问题的基本技术。在平凡(无句柄)曲面上的图形中，圈基数的行为与在非平凡曲面上的显著不同。因此，通过对这些问题的研究，进一步了解曲面图的性质，PI将为曲面图的算法设计提供下一步的工作。

Many computational problems start with a model that is a mesh or graph drawn on a surface. A classic example is the representation of a physical object for use in computer graphics systems by selecting points on the surface of the object and approximating the surface with triangles whose corners are the selected points: the points become the nodes and the sides of the triangles become the edges of a graph and the graph can be viewed as drawn on the surface of the object. When the surface is simpler, algorithms for manipulating a graph on the surface are more efficient; a surface is more complicated when it has features such as handles and holes. A common way to deal with these features is to simplify the surface by cutting the surface open to remove the handles and holes. This project will develop accurate and efficient methods for simplifying surfaces in this way as well as for other closely related problems. Because the problems are fundamental, new algorithms for them will provide efficient pre-processing tools for a wide range of applications. The PIs will involve graduate students in the research and, building on earlier successes and the fostering of a welcoming research environment, endeavor to recruit students from underrepresented populations.This project will address the above-described "cut-graph" problem as well as the problem of finding the minimum cycle-basis (a minimum-cost way to represent all the cycles in a graph) and the minimum homology-basis (a minimum-cost way to represent all the handles and holes in the surface on which the graph is drawn). For graphs on surfaces, these problems are very closely related. By considering these problems together, the PIs will develop fundamental techniques that will be translatable to other problems in these types of graphs. Cycle bases behave significantly differently in graphs on trivial (handle-free) surfaces than in non-trivial surfaces. For this reason, by further understanding the properties of surface graphs through the study of these problems, the PIs will provide the next step for algorithm design in surface graphs.