Collaborative Research: Algorithms for Graphs on Surfaces

点击翻译按钮获取中文摘要

NUMBER: 0830403INSTITUTION: University of California-IrvinePI: Goodrich, Michael T. & Eppstein, David A.TITLE: Collaborative Research: Algorithms for Graphs on SurfacesCollaborative with:NUMBER: 0830149INSTITUTION: Brown UniversityPI: Tamassia, RobertoTITLE: Collaborative Research: Algorithms for Graphs on SurfacesABSTRACTThis 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.