Combinatorial and Geometric Properties of Planar Laman Graphs
Combinatorial and Geometric Properties of Planar Laman Graphs
复制标题
平面拉曼图的组合和几何性质
DOI：
10.1137/1.9781611973105.120
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Kevin Verbeek
中科院分区：
文献类型：
--
作者：
S. Kobourov;T. Ueckerdt;Kevin Verbeek
拉曼图自然出现在结构力学和刚性理论中。具体来说，他们的特点是最低限度的刚性平面杆和关节系统，这是经常需要在机器人技术，以及在分子化学和聚合物物理。本文介绍了平面Laman图的三种新的组合结构：角结构、角标号和边标号。后两种结构与极大平面图的Schnyder实现子有关。证明了平面Laman图是一类角结构为树的图，称之为角树，并且每个角树都有相应的角标号和边标号.
使用这些强大的组合结构的组合，我们表明，每个平面拉曼图有一个L-接触表示，即平面拉曼图是轴对齐的L-形状的接触图。此外，我们表明，平面拉曼图及其子图是唯一的图，可以表示这种方式。
我们提出了有效的算法，计算，为每个平面拉曼图G，角树，角标签，边标签，并最终的L-接触表示的G。总的运行时间是O（n2），其中n是G的顶点数，并且L-接触表示是在n × n网格上实现的.
Laman graphs naturally arise in structural mechanics and rigidity theory. Specifically, they characterize minimally rigid planar bar-and-joint systems which are frequently needed in robotics, as well as in molecular chemistry and polymer physics. We introduce three new combinatorial structures for planar Laman graphs: angular structures, angle labelings, and edge labelings. The latter two structures are related to Schnyder realizers for maximally planar graphs. We prove that planar Laman graphs are exactly the class of graphs that have an angular structure that is a tree, called angular tree, and that every angular tree has a corresponding angle labeling and edge labeling.
Using a combination of these powerful combinatorial structures, we show that every planar Laman graph has an L-contact representation, that is, planar Laman graphs are contact graphs of axis-aligned L-shapes. Moreover, we show that planar Laman graphs and their subgraphs are the only graphs that can be represented this way.
We present efficient algorithms that compute, for every planar Laman graph G, an angular tree, angle labeling, edge labeling, and finally an L-contact representation of G. The overall running time is O(n2), where n is the number of vertices of G, and the L-contact representation is realized on the n X n grid.