TY - GEN

T1 - Combinatorial and geometric properties of planar Laman graphs

AU - Kobourov, Stephen

AU - Ueckerdt, Torsten

AU - Verbeek, Kevin

PY - 2013

Y1 - 2013

N2 - 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 Script O sign(n 2), where n is the number of vertices of G, and the L-contact representation is realized on the n x n grid.

AB - 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 Script O sign(n 2), where n is the number of vertices of G, and the L-contact representation is realized on the n x n grid.

UR - http://www.scopus.com/inward/record.url?scp=84876020688&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84876020688&partnerID=8YFLogxK

U2 - 10.1137/1.9781611973105.120

DO - 10.1137/1.9781611973105.120

M3 - Conference contribution

AN - SCOPUS:84876020688

SN - 9781611972511

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 1668

EP - 1678

BT - Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013

PB - Association for Computing Machinery

T2 - 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013

Y2 - 6 January 2013 through 8 January 2013

ER -