Combinatorial pseudo-Triangulations

Details Combinatorial pseudo-Triangulations Combinatorial pseudo-Triangulations

2003-07-29

arxiv.org/abs/math/0307370v3

Discrete Mathematics 307:3-5, (2007), 554-566

Mathematics

Combinatorics

17 pages, 10 figures. Changes from v2: minor editing plus removal of a superfluous lemma. Changes from v1: Section 5 has been

Scientific paper

10.1016/j.disc.2005.09.045

We prove that a planar graph is generically rigid in the plane if and only if it can be embedded as a pseudo-triangulation. This generalizes the main result of math.CO/0307347 which treats the minimally generically rigid case. The proof uses the concept of combinatorial pseudo-triangulation, CPT, in the plane and has two main steps: showing that a certain ``generalized Laman property'' is a necessary and sufficient condition for a CPT to be ``stretchable'', and showing that all generically rigid plane graphs admit a CPT assignment with that property. Additionally, we propose the study of combinatorial pseudo-triangulations on closed surfaces.

Affiliated with

Also associated with

No associations

Rating

Combinatorial 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 Combinatorial pseudo-Triangulations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Combinatorial pseudo-Triangulations will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-542