Michael Goodrich and David Eppstein, both Distinguished Professors of Computer Science in UCI’s Donald Bren School of Information and Computer Sciences (ICS), have been awarded a National Science Foundation (NSF) grant to study algorithms for geometric graphs. They will be receiving $800,000 over the next four years for their work on this project, which is a collaboration with Computer Science Professor Stephen Kobourov of the University of Arizona. Kobourov will receive $400,000 over the next four years, bringing the total budget to $1.2 million.

As noted in the project abstract, geometric graphs are “structures that realize the relationships of a combinatorial graph — that is, a set of elements called ‘nodes’ or ‘vertices’ and a set of pairwise relationships between them, such as would be determined by a social network or road network.” They appear in a wide range of applications, including physics, data visualization, computational biology and data forensics. The goal of this work is to develop algorithms that faithfully represent the geometric realizations of such graphs.

“Our project will study geometric graphs both as inputs and as outputs,” says Goodrich. “For instance, geometric graphs are input from geographic datasets such as road networks, and they are output as data visualizations of relationships between objects arising from applications such as network analysis, combinatorics and bioinformatics.”

The researchers aim to improve methods for dealing with geometric graphs, benefiting related applications, such as data visualization or automobile navigation.

“I’m excited to work with Professors Goodrich and Kobourov on the topics of this proposal,” says Eppstein, “which range widely from theoretical problems in discrete geometry to practical problems of visualizing population density and constructing fair subdivisions of geographic regions.”

— Shani Murray