Planar Minimally Rigid Graphs and Pseudo-Triangulations

Abstract

Pointed pseudo-triangulations are planar minimally rigid graphs embedded in the plane with pointed vertices (adjacent to an angle larger than 180 degrees. In this paper we prove that the opposite statement is also true, namely that planar minimally rigid graphs always admit pointed embeddings, even under certain natural topological and combinatorial constraints. We provide two proofs, which both yield efficient embedding algorithms. One based on Henneberg inductive constructions from combinatorial rigidity theory, the other on a generalization of Tutte's barycentric embeddings to directed graphs.

25 pages, 12 figures. A preliminary version appeared in the proceedings of the 19th ACM Symposium on Computational Geometry, San Diego, June 8-10, 2003

References in corpus (3)

• Expansive Motions and the Polytope of Pointed Pseudo-Triangulations
• The polytope of non-crossing graphs on a planar point set
• Non-crossing frameworks with non-crossing reciprocals

Cited by in corpus (25)

• Controlling rigid formations of mobile agents under inconsistent measurements
• Multitriangulations, pseudotriangulations and primitive sorting networks
• On the Number of Pseudo-Triangulations of Certain Point Sets
• The polytope of non-crossing graphs on a planar point set
• Combinatorial pseudo-Triangulations
• Contact Representations of Sparse Planar Graphs
• Maximizing Maximal Angles for Plane Straight-Line Graphs
• Planar pseudo-triangulations, spherical pseudo-tilings and hyperbolic virtual polytopes
• Exact Camera Location Recovery by Least Unsquared Deviations
• Multitriangulations, pseudotriangulations and some problems of realization of polytopes
• Corner-Sharing Tetrahedra for Modeling Micro-Structure
• Laman Graphs are Generically Bearing Rigid in Arbitrary Dimensions
• Bearing Rigidity Theory and its Applications for Control and Estimation of Network Systems: Life Beyond Distance Rigidity
• Ultrarigid periodic frameworks
• Discrete Object Generation with Reversible Inductive Construction
• Angle Covers: Algorithms and Complexity
• The combinatorial geometry of stresses in frameworks
• Binary Labelings for Plane Quadrangulations and their Relatives
• Undirected Rigid Formations are Problematic
• Geometry of configuration spaces of tensegrities
• Graph theory inspired anomaly detection at the LHC
• Symmetric contact systems of segments, pseudotriangulations and inductive constructions for corresponding surface graphs
• Rigidity with few locations
• Mixed Volume Techniques for Embeddings of Laman Graphs
• Equilateral L-Contact Graphs