Eppstein awarded two NSF grants for algorithm research

Chancellor’s Professor of Computer Science David Eppstein was awarded two National Science Foundation (NSF) grants totaling $575,881 in support of his research projects “Collaborative Research: Efficient Algorithms for Cycles on Surfaces” and “Sparse Geometric Graph Algorithms.” The grant period for both projects is set to run between August 2016 and July 2019.

Many real-world problems can be modeled by geometric graphs. For instance, road networks may be represented by vertices as intersections or junctions of roads, while the edges represent the segments of road between two consecutive intersections. Eppstein’s research will cover a broad range of topics within computational geometry and graph algorithms. Eppstein is the sole PI for both NSF projects, which will work to solve common real-world problems in graph applications. “Collaborative Research: Efficient Algorithms for Cycles on Surfaces” will focus on developing accurate and efficient methods for simplifying surfaces related to “cut-graph” problems, as well as for other closely related complications. “Sparse Geometric Graph Algorithms” will concentrate on issues related to geometric graphs, such as the large collection of problems from application areas where sparse geometric graphs naturally arise.