Collaborative Research: AF: Medium: Algorithms for Geometric Graphs

点击翻译按钮获取中文摘要

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.