TY - JOUR

T1 - Flip graphs of bounded-degree triangulations

AU - Aichholzer, O.

AU - Hackl, T.

AU - Orden, D.

AU - Ramos, P.

AU - Rote, G.

AU - Schulz, A.

AU - Speckmann, B.

PY - 2013

Y1 - 2013

N2 - 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

AB - 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

U2 - 10.1007/s00373-012-1229-0

DO - 10.1007/s00373-012-1229-0

M3 - Article

VL - 29

SP - 1577

EP - 1593

JO - Graphs and Combinatorics

JF - Graphs and Combinatorics

SN - 0911-0119

IS - 6

ER -