Flip graphs of bounded-degree triangulations

O. Aichholzer, T. Hackl, D. Orden, P. Ramos, G. Rote, A. Schulz, B. Speckmann

Research output: Contribution to journalArticleAcademicpeer-review

1 Downloads (Pure)


We study ¿ip graphs of triangulations whose maximum vertex degree is bounded by a constant k. In particular, we consider triangulations of sets of n points in convex position in the plane and prove that their ¿ip graph is connected if and only if k > 6; the diameter of the ¿ip graph is O(n2). We also show that, for general point sets, ¿ip graphs of pointed pseudo-triangulations can be disconnected for k = 9, and ¿ip graphs of triangulations can be disconnected for any k. Additionally, we consider a relaxed version of the original problem. We allow the violation of the degree bound k by a small constant. Any two triangulations with maximum degree at most k of a convex point set are connected in the ¿ip graph by a path of length O(n log n), where every intermediate triangulation has maximum degree at most k + 4. Keywords: Flip graphs - Triangulations - Rotation distance - Connectivity - Degree bounds
Original languageEnglish
Pages (from-to)1577-1593
Number of pages17
JournalGraphs and Combinatorics
Issue number6
Publication statusPublished - 2013


Dive into the research topics of 'Flip graphs of bounded-degree triangulations'. Together they form a unique fingerprint.

Cite this