Ruth Haas, David Orden, Günter Rote, Francisco Santos,
Brigitte
Servatius, Herman Servatius, Diane Souvaine, Ileana Streinu, and Walter
Whiteley:
Planar minimally rigid graphs and pseudo-triangulations
- in: Proceedings of the Nineteenth Annual Symposium on Computational
Geometry, San Diego, June 8–10, 2003. Association for
Computing Machinery, 2003, pp. 154–163. doi:10.1145/777792.777817
- Computational Geometry, Theory and Applications 31
(2005), 31–61. doi:10.1016/j.comgeo.2004.07.003, arXiv:math.CO/0307347.
(This is an
extended version of parts of the results of 1.)
Abstract
Pointed pseudo-triangulations are planar minimally rigid graphs
embedded in the
plane with pointed vertices (adjacent to an angle larger than
pi). 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. The proofs
yield
efficient embedding algorithms. They also provide the first
algorithmically
effective result on graph embeddings with oriented matroid constraints
other
than convexity of faces. These constraints are described by combinatorial
pseudo-triangulations, first defined and studied in this paper.
Also of
interest are our two proof techniques, one based on Henneberg inductive
constructions from combinatorial rigidity theory, the other on a
generalization
of Tutte's barycentric embeddings to directed graphs.
Last update: April 5, 2005.