Research Funding:
Algorithms for Graphs on Surfaces
Support provided by National Science Foundation
Description
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.
Principal Investigator
Co-PIs
Projects Supported
Details
Amount: | 199999 |
Dates: | September 2008 - August 2011 |
Status: | Active |
Page Owner: Amy Tarbox
|
Last Modified: Fri Mar 13 14:09:54 2009
|