Combinatorial pseudo-Triangulations
| dc.creator | Orden, David | |
| dc.creator | Santos, Francisco | |
| dc.creator | Servatius, Brigitte | |
| dc.creator | Servatius, Herman | |
| dc.date | 2003-07-29 | |
| dc.date | 2005-10-31 | |
| dc.date.accessioned | 2026-07-07T08:02:54Z | |
| dc.date.available | 2026-07-07T08:02:54Z | |
| dc.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. | |
| dc.description | 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" | |
| dc.identifier | https://arxiv.org/abs/math/0307370 | |
| dc.identifier | http://arxiv.org/abs/math/0307370 | |
| dc.identifier | Discrete Mathematics 307:3-5, (2007), 554-566 | |
| dc.identifier | doi:10.1016/j.disc.2005.09.045 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/129382 | |
| dc.subject | Combinatorics | |
| dc.subject | Metric Geometry | |
| dc.subject | 05C10; 05C62 | |
| dc.title | Combinatorial pseudo-Triangulations | |
| dc.type | text |