Flip graphs of bounded-degree triangulations

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

doi:10.1016/j.endm.2009.07.084

Flip graphs of bounded-degree triangulations

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

Research output: Contribution to journal › Article › Academic › peer-review

1 Citation (Scopus)

Abstract

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.

Original language	English
Pages (from-to)	509-513
Journal	Electronic Notes in Discrete Mathematics
Volume	34
DOIs	https://doi.org/10.1016/j.endm.2009.07.084
Publication status	Published - 2009

Access to Document

10.1016/j.endm.2009.07.084

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

Cite this

@article{5d03f2c544e44015aefa089289a0e93d,

title = "Flip graphs of bounded-degree triangulations",

abstract = "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.",

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

year = "2009",

doi = "10.1016/j.endm.2009.07.084",

language = "English",

volume = "34",

pages = "509--513",

journal = "Electronic Notes in Discrete Mathematics",

issn = "1571-0653",

publisher = "Elsevier",

}

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 -