AF:SMALL:Sparse Geometric Graph Algorithms

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

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.