Collaborative Research: Algorithms for Graphs on Surfaces

Brown University, Providence RI

Investigators

Abstract

NUMBER: 0830403 INSTITUTION: University of California-Irvine PI: Goodrich, Michael T. & Eppstein, David A. TITLE: Collaborative Research: Algorithms for Graphs on Surfaces Collaborative with: NUMBER: 0830149 INSTITUTION: Brown University PI: Tamassia, Roberto TITLE: Collaborative Research: Algorithms for Graphs on Surfaces ABSTRACT This project addresses fundamental questions on geometric and spatial aspects of graphs and networks, with applications to road networks, sensor networks, computer networks, and social networks. In particular, methods will be developed for constructing effective geometric layouts of networks on surfaces and in three-dimensional space and for analyzing properties of networks by exploiting their geometric structure. The focus of the project is the design and analysis of algorithms for graphs on surfaces in the following three thrust areas: (1) algorithms for embedding graphs on surfaces, including methods for greedy embeddings of graphs to facilitate geometric routing, algorithms for manifold triangulation for a set of points sampled from an embedded surface, and techniques for drawing trees in the plane; (2) algorithms for graphs embedded on surfaces, including the study of connections between partial cubes and integer lattices, the development of algorithms for graphs embedded in non-Euclidean spaces, and the design of methods for solving graph problems on quadrilateral meshes; (3) applications of algorithms for graphs on surfaces, including applications of geometric graphs to computer security and algorithms for road networks.