Combinatorial pseudo-Triangulations
Loading...
Date
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Description
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.
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"
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"