Collaborative Research: Algorithms for Graphs on Surfaces

编号：0830403机构：加州大学欧文分校PI：古德里奇，迈克尔T. &Eppstein，大卫A.标题：合作研究：表面上的图的算法合作单位：编号：0830149研究机构：布朗大学PI：Tamassia，Roberto标题：合作研究：表面上的图的算法摘要该项目解决了图形和网络的几何和空间方面的基本问题，并应用于道路网络，传感器网络，计算机网络和社交网络。特别是，将开发用于在表面上和三维空间中构建网络的有效几何布局的方法，以及通过利用其几何结构来分析网络属性的方法。该项目的重点是设计和分析以下三个方面的曲面上的图的算法：（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.