Flip Graphs of Degree-Bounded (Pseudo-)Triangulations

Details Flip Graphs of Degree-Bounded (Pseudo-)Triangulations Flip Graphs of Degree-Bounded (Pseudo-)Triangulations

2009-03-12

arxiv.org/abs/0903.2184v1

Mathematics

Combinatorics

9 pages, 12 figures

Scientific paper

We study flip graphs of (pseudo-)triangulations whose maximum vertex degree is bounded by a constant k. In particular, we consider (pseudo-)triangulations of sets of n points in convex position in the plane and prove that their flip graph is connected if and only if k > 6; the diameter of the flip graph is O(n^2). We also show that for general point sets flip graphs of minimum pseudo-triangulations can be disconnected for k < 10, and flip graphs of triangulations can be disconnected for any k.

Affiliated with

Also associated with

No associations

Rating

Flip Graphs of Degree-Bounded (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 Flip Graphs of Degree-Bounded (Pseudo-)Triangulations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Flip Graphs of Degree-Bounded (Pseudo-)Triangulations will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-36648