AF:Small:Geometric graph algorithms

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

The investigator studies algorithms for problems that combine graph theory with geometry.One component of the proposal concerns sets of circles that do not overlap, but meet at points of tangency like coins pushed together on the surface of a table. The investigator will seek out efficient algorithms for constructing circle packings and use them to find "Lombardi drawings", a form of information visualization in which graph edges are represented as circular arcs. These drawings resemble soap bubbles and the PI plans to use them to characterize the patterns of adjacency that soap bubbles can have.A second component of the proposal concerns the graphs formed from geometric objects by linking nearby pairs of objects by edges; these graphs have many applications in data clustering, collision detection in physical simulation, and architectural design. The investigator will develop efficient data structures for maintaining mutual nearest neighbors of dynamic points, and study nearest neighbors in tree-like non-Euclidean metric spaces for which previously known methods are inapplicable.In a third component of the award, the investigator will study efficient algorithms for constructing cartograms, visualizations of geographic data in which geographic regions are shown with stylized shapes and distorted areas that represent numeric information such as population. In addition he will study compact three-dimensional visualizations of graphs as the sets of vertices and edges of three-dimensional polyhedra with axis-parallel edges and to study Barnette's conjecture on Hamiltonian cycles for the graphs of axis-parallel polyhedra.As well as the applications of these problems in information visualization, scientific computing, and engineering, the broader impacts of this proposal include open-source implementations of algorithms and the public dissemination of knowledge via the creation of relevant Wikipedia articles.