Planar minimally rigid graphs and pseudo-triangulations

Graph representations (geometric and intersection representations, etc.) (05C62) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Graph theory (including graph drawing) in computer science (68R10)

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.

Review text

In order to answer a question passed by \textit{I. Streinu} [S. Basu et. al. (eds), Proc. DIMACS Workshop, Algorithmic and Quantitative Aspects of Real Algebraic Geometry in Mathematics and Computer Science, 181-205 (2003; Zbl 1056.68158)], the authors prove as the main theorem that every planar Laman graph can be embedded as a pointed pseudo-triangulation. This result is extended along several lines, leading to interesting combinatorial objects to study. In particular it is shown that any combinatorial pseudo-triangulation of a plane Laman graph or of a plane rigidity circuit is stretchable. Some open problems are also suggested. The authors also mention that a preliminary version of this paper appeared in [\textit{R. Haas}, et al. Proc. 19th Ann. Symp. Comput. Geometry, 154--163 (2003)]

Recommendations

Cites work

Cited in

(43)

This page was built for publication: Planar minimally rigid graphs and pseudo-triangulations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1775778)