Collaborative Research: Algorithms for Graphs on Surfaces

编号：0830403机构：加州大学欧文分校i: Goodrich， Michael T. & epppstein, David a .标题：合作研究：曲面上图的算法协作与：编号：0830147机构：布朗大学i: Tamassia， RobertoTITLE：合作研究：摘要本项目探讨图形和网络的几何和空间方面的基本问题，并将其应用于道路网络、传感器网络、计算机网络和社会网络。特别是，将开发的方法，以建立有效的几何布局的网络在表面和三维空间，并分析网络的性质，利用其几何结构。该项目的重点是在以下三个重点领域设计和分析曲面上图形的算法：(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.