Planar Minimally Rigid Graphs and Pseudo-Triangulations

Details Planar Minimally Rigid Graphs and Pseudo-Triangulations Planar Minimally Rigid Graphs and Pseudo-Triangulations

2003-07-25

arxiv.org/abs/math/0307347v1

Computational Geometry: theory and Applications 31:1-2 (May 2005), 63-100.

Mathematics

Combinatorics

25 pages, 12 figures. A preliminary version appeared in the proceedings of the 19th ACM Symposium on Computational Geometry, S

Scientific paper

10.1016/j.comgeo.2004.07.003

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.

Affiliated with

Also associated with

No associations

Rating

Planar Minimally Rigid Graphs and Pseudo-Triangulations does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Planar Minimally Rigid Graphs and Pseudo-Triangulations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Planar Minimally Rigid Graphs and Pseudo-Triangulations will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-50193