AF:SMALL:Sparse Geometric Graph Algorithms

University Of California-Irvine, Irvine CA

Investigators

Abstract

Many real-world problems can be modeled by geometric graphs: systems of vertices that represent geometric objects and edges that represent connections or interactions between pairs of these objects. For instance, the vertices of a road network may represent intersections or junctions of roads, while the edges represent the segments of road between two consecutive intersections. Although these graphs are not planar (a road can cross a bridge without intersecting the road beneath), such crossings are uncommon, and the project will investigate ways of exploiting that sparse crossing structure to efficiently solve problems such as route planning on road networks. Similarly, the project will investigate the structure of the underlying geometric graphs, and the use of that structure to develop efficient algorithms, for other problems that include the visualization of hierarchically clustered networks, pattern mining in social networks, splitting large scientific simulations into smaller subproblems with low amounts of interaction between the subproblems, the analysis of mechanical systems of rigid parts connected by hinges, the design of maps that distort geographic areas to display other types of quantitative information, and the visualization of overlaps between fragments of DNA sequences. The project proposes attacks on a large collection of problems from application areas where sparse geometric graphs naturally arise. The project suggests a model for real-world road networks in which a derived graph of edges and their crossings has bounded degeneracy, and seeks to investigate how sparsity properties of this crossing graph affect the underlying road graph. The project seeks to determine whether it is hard to recognize the graphs of 4-polytopes and simple 4-polytopes, and whether a recognition algorithm of the investigator for a special class of 4-polytopes can be extended to a realization algorithm. The graphs in this class have small separators, and the project seeks to determine whether this is true more generally for certain graphs derived from planar clustered graph drawings. The project seeks efficient data structures that maintain low-degeneracy orientations of a dynamic graph and use these orientations to quickly find features in the graph, needed when fitting social networks to exponential random graph models. Finite element meshes with bounded aspect ratio for each element have small separators, but arbitrary tetrahedral meshes do not. The project seeks intermediate conditions on the shape of the elements in a mesh that would ensure the existence of small separators. The graphs arising in kinematic analysis can be characterized by linear bounds on the edges in each subgraph, and recognized in quadratic time by a pebbling algorithm. The project seeks more efficient algorithms to test the rigidity or degrees of freedom of mechanical structures in subquadratic time. Subdivisions of rectangles into smaller rectangles have applications in architectural design, cartographic information visualization, and VLSI design. An area-universal subdivision is one that can fit any assignment of areas to its rectangles. The project seeks efficient algorithms to construct area-universal subdivisions as well as subdivisions produced by a recursive splitting process. Unit interval graphs arise in modeling human preferences and in DNA physical mapping. Some problems that are hard on broader graph classes can be solved efficiently on unit interval graphs by representing the graph using a binary sequence and applying a finite automaton to the sequence. The project seeks a more general explanation of this phenomenon. In graph drawing, styles of graph drawing on the basis that are somewhere-dense allow all graphs to be drawn in that style with constant bends per edge while nowhere dense styles require an unbounded number of bends per edge. The project seeks a theory of sparsity distinguishing nowhere-dense styles that require many bends per edge from those that require few bends. Additional components of the project include questions on diameter graphs and book thickness.