Flip graphs of bounded-degree triangulations

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

Research output: Contribution to journalArticleAcademicpeer-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 languageEnglish
Pages (from-to)509-513
JournalElectronic Notes in Discrete Mathematics
Volume34
DOIs
Publication statusPublished - 2009

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

Cite this