Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4649080 | Discrete Mathematics | 2007 | 13 Pages |
Abstract
We prove that a planar graph is generically rigid in the plane if and only if it can be embedded as a pseudo-triangulation. This generalizes the main result of [Haas et al. Planar minimally rigid graphs and pseudo-triangulations, Comput. Geom. 31(1–2) (2005) 31–61] which treats the minimally generically rigid case.The proof uses the concept of combinatorial pseudo-triangulation, CPT, in the plane and has two main steps: showing that a certain “generalized Laman property” is a necessary and sufficient condition for a CPT to be “stretchable”, and showing that all generically rigid plane graphs admit a CPT assignment with that property.Additionally, we propose the study of CPTs on closed surfaces.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
David Orden, Francisco Santos, Brigitte Servatius, Herman Servatius,