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 - 2009
Y1 - 2009
N2 - We study flip graphs of triangulations whose maximum vertex degree is bounded by a constant k. Specifically, we consider 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(n2). We also show that for general point sets, flip graphs of triangulations with degree k can be disconnected for any k.
AB - We study flip graphs of triangulations whose maximum vertex degree is bounded by a constant k. Specifically, we consider 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(n2). We also show that for general point sets, flip graphs of triangulations with degree k can be disconnected for any k.
U2 - 10.1016/j.endm.2009.07.084
DO - 10.1016/j.endm.2009.07.084
M3 - Article
VL - 34
SP - 509
EP - 513
JO - Electronic Notes in Discrete Mathematics
JF - Electronic Notes in Discrete Mathematics
SN - 1571-0653
ER -