2003/07/25 by Ruth Haas, David Orden, Guenter Rote +8 · 1 citation
Computer Science · Engineering · Mathematics · #1-planar graph #Advanced Materials and Mechanics #Artificial intelligence #Book embedding #Chordal graph #Combinatorics #Computational Geometry and Mesh Generation #Computer graphics (images) #Computer science #Discrete mathematics #Embedding #Generalization #Geometry #Graph #Mathematical analysis #Mathematical proof #Mathematics #Physics #Planar #Planar graph #Plane (geometry) #Rigidity (electromagnetism) #Statement (logic) #Structural Analysis and Optimization #math.CO #math.MG #msc:05C10 #msc:05C62
paper · pdf · doi:10.1016/j.comgeo.2004.07.003
published as Computational Geometry: theory and Applications 31:1-2 (May 2005), 63-100. · 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
arxiv created 2003/07/25 · openalex publication_date 2004/12/10 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/06
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.