Planar minimally rigid graphs and pseudo-triangulations (Q1775778)

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)]