AF:SMALL:Sparse Geometric Graph Algorithms

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

Many real-world problems can be modeled by geometric graphs: systemsof vertices that represent geometric objects and edges that representconnections or interactions between pairs of these objects. Forinstance, the vertices of a road network may represent intersectionsor junctions of roads, while the edges represent the segments of roadbetween two consecutive intersections. Although these graphs are notplanar (a road can cross a bridge without intersecting the road beneath), such crossings areuncommon, and the project will investigate ways of exploiting thatsparse crossing structure to efficiently solve problems such as routeplanning on road networks. Similarly, the project will investigate thestructure of the underlying geometric graphs, and the use of thatstructure to develop efficient algorithms, for other problems thatinclude the visualization of hierarchically clustered networks,pattern mining in social networks, splitting large scientificsimulations into smaller subproblems with low amounts of interactionbetween the subproblems, the analysis of mechanical systems of rigidparts connected by hinges, the design of maps that distort geographicareas to display other types of quantitative information, and thevisualization of overlaps between fragments of DNA sequences.The project proposes attacks on a large collection of problems fromapplication areas where sparse geometric graphs naturally arise. Theproject suggests a model for real-world road networks in which aderived graph of edges and their crossings has bounded degeneracy, andseeks to investigate how sparsity properties of this crossing graphaffect the underlying road graph. The project seeks to determinewhether it is hard to recognize the graphs of 4-polytopes and simple4-polytopes, and whether a recognition algorithm of the investigatorfor a special class of 4-polytopes can be extended to a realizationalgorithm. The graphs in this class have small separators, and theproject seeks to determine whether this is true more generally forcertain graphs derived from planar clustered graph drawings. Theproject seeks efficient data structures that maintain low-degeneracyorientations of a dynamic graph and use these orientations to quicklyfind features in the graph, needed when fitting social networks toexponential random graph models. Finite element meshes with boundedaspect ratio for each element have small separators, but arbitrarytetrahedral meshes do not. The project seeks intermediate conditionson the shape of the elements in a mesh that would ensure the existenceof small separators. The graphs arising in kinematic analysis can becharacterized by linear bounds on the edges in each subgraph, andrecognized in quadratic time by a pebbling algorithm. The projectseeks more efficient algorithms to test the rigidity or degrees offreedom of mechanical structures in subquadratic time. Subdivisions ofrectangles into smaller rectangles have applications in architecturaldesign, cartographic information visualization, and VLSI design. Anarea-universal subdivision is one that can fit any assignment of areasto its rectangles. The project seeks efficient algorithms to constructarea-universal subdivisions as well as subdivisions produced by arecursive splitting process. Unit interval graphs arise in modelinghuman preferences and in DNA physical mapping. Some problems that arehard on broader graph classes can be solved efficiently on unitinterval graphs by representing the graph using a binary sequence andapplying a finite automaton to the sequence. The project seeks a moregeneral explanation of this phenomenon. In graph drawing, styles ofgraph drawing on the basis that are somewhere-dense allow all graphsto be drawn in that style with constant bends per edge while nowheredense styles require an unbounded number of bends per edge. Theproject seeks a theory of sparsity distinguishing nowhere-dense stylesthat require many bends per edge from those that require fewbends. Additional components of the project include questions ondiameter graphs and book thickness.