Collaborative Research: Algorithms for Graphs on Surfaces

编号：0830403机构：加州大学欧文分校PI：Goodrich，Michael T.&Amp；Eppstein，David A.TITLE：合作研究：表面图形的算法与：编号：0830149合作：布朗大学PI：Tamassia，RobertoTITLE：合作研究：表面图形的算法ABSTRACT这个项目解决了图形和网络的几何和空间方面的基本问题，以及对道路网络、传感器网络、计算机网络和社会网络的应用。特别是，将开发出在表面和三维空间中构建网络的有效几何布局的方法，并通过利用网络的几何结构来分析网络的性质。该项目的重点是以下三个方面的曲面图形算法的设计和分析：(1)曲面图形的嵌入算法，包括图形的贪婪嵌入方法以便于几何布线，从嵌入曲面上采样的一组点的流形三角剖分算法，以及在平面上绘制树的技术；(2)曲面图形的嵌入算法，包括部分立方体和整数格之间的联系的研究，非欧几里德空间图形嵌入算法的开发，以及四边形网格上图形问题的求解方法的设计；(3)曲面图形算法的应用，包括几何图形在计算机安全中的应用和道路网络算法。

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.