Collaborative Research: Algorithms for Graphs on Surfaces

协作研究：曲面图的算法

基本信息

批准号：
0830403
负责人：
Michael Goodrich
金额：
$ 40万
依托单位：
University of California-Irvine
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2008
资助国家：
美国
起止时间：
2008-09-01 至 2013-08-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=0830403&HistoricalAwards=false
关键词：
Collaborative Research Algorithms Graphs 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.

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解决有关图形和网络的几何和空间方面的基本问题，并在道路网络，传感器网络，计算机网络和社交网络上进行应用。特别是，将开发用于在表面和三维空间中构建有效网络的有效几何布局的方法，并通过利用其几何结构来分析网络的性质。该项目的重点是在以下三个推力区域中的图形算法的设计和分析：（1）将图形嵌入在表面上的算法，包括图形贪婪嵌入的贪婪嵌入的方法，以促进几何路由，示意绘制绘制绘制的平面算法的算法，并构造了绘制的绘制和技术，并构造了均匀的绘制和技术的效果和技术。（2）嵌入在表面上的图形算法，包括研究部分立方体和整数晶格之间的连接，嵌入非欧基群空间中图的算法的开发以及在四边形网格上求解图形问题的方法的设计；（3）算法在表面上的图形应用程序，包括将几何图表到计算机安全性和道路网络算法的应用。