Collaborative Research: AF: Medium: Algorithms for Geometric Graphs

合作研究：AF：媒介：几何图算法

基本信息

批准号：
2212129
负责人：
Michael Goodrich
金额：
$ 79.98万
依托单位：
University of California-Irvine
依托单位国家：
美国
项目类别：
Continuing Grant
财政年份：
2022
资助国家：
美国
起止时间：
2022-06-15 至 2026-05-31
项目状态：
未结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=2212129&HistoricalAwards=false
关键词：
Collaborative Research AF Medium Algorithms

项目摘要

This project studies geometric graphs. These are geometric structures that realize the relationships of a combinatorial graph, that is, a set of elements called “nodes” or “vertices” and a set of pairwise relationships between them, such as would be determined by a social network or road network. Geometric graphs arise in a wide range of applications, including physics, data visualization, computational biology, and data forensics. Any such graph can be realized in a geometric space, so that the nodes of the graph are points in the space and relationships between nodes are represented by line segments or curves connecting pairs of nodes. These geometric realizations of combinatorial graphs can then be measured in terms of how well they achieve various parameters, such as area, edge length, angle separation, etc. Indeed, the research area of graph drawing is exclusively focused on algorithms for producing good (faithful and representative) geometric realizations of graphs. Improved methods for dealing with geometric graphs can benefit any application, such as data visualization or automobile navigation, that generates or uses geometric graphs.The goals of this project are broadly organized around the following two themes: (1) Algorithms for producing geometric realizations of graphs. This theme is directed at algorithms and complexity bounds for producing geometric realizations of graphs, including considerations of complexity measures such as area, edge length, edge bends, edge crossings, etc. (2) Algorithms on geometric graphs. This theme is directed at algorithms that take as input geometric graphs, such as road networks, with the goal of achieving complexity bounds that are improved over those possible for general graphs.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

该项目研究几何图。这些几何结构实现了组合图的关系，即一组称为“节点”或“顶点”的元素，以及它们之间的一组成对关系，例如由社交网络或道路网络确定。几何图出现在广泛的应用中，包括物理，数据可视化，计算生物学和数据取证。任何此类图都可以在几何空间中实现，因此图的节点是空间中的点，节点之间的关系由线段或连接节点对的曲线表示。然后，可以根据它们达到各种参数的能力，例如面积，边缘长度，角度分离等，可以测量组合图的这些几何实现。的确，图形图的研究领域仅集中在产生良好（忠实和代表性的）几何学实现图的算法上。处理几何图的改进方法可以使生成或使用几何图的任何应用程序（例如数据可视化或汽车导航）受益。该项目的目标围绕以下两个主题进行了广泛组织：（1）用于产生图形几何实现的算法。该主题针对算法和复杂性界限，用于产生图形的几何实现，包括考虑复杂性测量值，例如面积，边缘长度，边缘弯曲，边缘交叉等。（2）几何图上的算法。该主题针对算法，这些算法将作为输入几何图（例如道路网络），其目的是实现复杂性界限，而复杂性范围比一般图表的可能性改进了。该奖项反映了NSF的法定任务，并被认为是通过基金会的知识分子和更广泛影响的审查审查标准来通过评估来通过评估来获得的支持。