Flip graphs of bounded-degree triangulations

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

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer 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
Originele taal-2Engels
Pagina's (van-tot)1577-1593
Aantal pagina's17
TijdschriftGraphs and Combinatorics
Nummer van het tijdschrift6
StatusGepubliceerd - 2013

Vingerafdruk Duik in de onderzoeksthema's van 'Flip graphs of bounded-degree triangulations'. Samen vormen ze een unieke vingerafdruk.

Citeer dit