2003/07/31 by David Orden, Francisco Santos, Brigitte Servatius +1
Computer Science · Engineering · Mathematics · #Advanced Materials and Mechanics #Computational Geometry and Mesh Generation #Structural Analysis and Optimization #math.CO #math.MG #msc:05C10 #msc:05C62
paper · pdf · doi:10.1016/j.disc.2005.09.045
published as Discrete Mathematics 307:3-5, (2007), 554-566 · 17 pages, 10 figures. Changes from v2: minor editing plus removal of a superfluous lemma. Changes from v1: Section 5 has been completely rewritten, after a referee complained (rightfully) that too many details were omitted. The rest only has minor corrections and stylistic changes. This version has been accepted in "Discrete Mathematics"
arxiv created 2005/10/31 · openalex publication_date 2006/09/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 math.CO/0307347 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 combinatorial pseudo-triangulations on closed surfaces.