AF:SMALL:Sparse Geometric Graph Algorithms

许多现实世界的问题都可以用几何图形来建模：表示几何对象的系统软件顶点和表示这些对象对之间的连接或交互的边缘。例如，道路网络的顶点可以表示道路的交叉路口或交叉点，而边缘表示两个连续交叉路口之间的道路段。尽管这些图不是平面的（一条道路可以穿过桥梁而不与下面的道路相交），但这样的交叉路口并不常见，该项目将研究利用这种稀疏的交叉结构来有效解决道路网络路线规划等问题的方法。同样，该项目将研究底层几何图形的结构，并利用该结构开发有效的算法，用于其他问题，包括分层聚类网络的可视化、社交网络中的模式挖掘、将大型科学模拟分解为子问题之间交互性较低的较小子问题、分析铰链连接的刚性部件的机械系统、扭曲地理区域以显示其他类型定量信息的地图设计，以及DNA序列片段之间重叠部分的可视化。该项目提出了针对稀疏几何图自然出现的应用领域的大量问题的攻击。该项目提出了一个现实世界道路网络的模型，其中导出的边缘图及其交叉点具有有限简并性，并试图研究该交叉点图的稀疏性如何影响底层道路图。该项目旨在确定4-多面体和简单4-多面体的图是否难以识别，以及研究者对一类特殊的4-多面体的识别算法是否可以扩展为实现算法。本课程中的图形具有较小的分隔符，该项目旨在确定这是否适用于来自平面聚类图形的某些图形。该项目寻求有效的数据结构，保持动态图的低退化方向，并使用这些方向快速找到图中的特征，当将社交网络拟合到指数随机图模型时需要。每个单元的有界纵横比的有限元网格有小的分隔符，但任意四面体网格没有。该项目寻求网格中元素形状的中间条件，以确保小型分离器的存在。在运动分析中产生的图形可以用每个子图的边缘上的线性边界来表征，并且可以在二次时间内用逐点算法进行识别。该项目寻求更有效的算法在次二次时间内测试机械结构的刚度或自由度。将矩形细分为更小的矩形在建筑设计、地图信息可视化和超大规模集成电路设计中都有应用。无区域通用细分是一种可以将任何区域分配适合其矩形的细分。该项目寻求有效的算法来构建区域通用细分以及由递归分裂过程产生的细分。单位间隔图出现在人类偏好建模和DNA物理制图中。一些在广义图类上难以解决的问题可以在单位区间图上有效地解决，方法是使用二进制序列表示图，并对序列应用有限自动机。该项目寻求对这一现象的更普遍的解释。在图形绘制中，基于某处密集的图形绘制样式允许以该样式绘制所有图形，每条边具有恒定的弯曲次数，而没有任何密集样式要求每条边无限的弯曲次数。该项目寻求一种稀疏性理论，以区分每条边需要多次弯曲的无密度样式和需要少量弯曲的样式。项目的其他组成部分包括直径图和书本厚度的问题。

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.