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 -