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

University Of California-Irvine, Irvine CA

Investigators

Abstract

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.