Collaborative Research: AF: Medium: Algorithms for Geometric Graphs

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

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.