{
  "id": "0903.2184",
  "version": "v5",
  "published": "2009-03-12T15:55:12.000Z",
  "updated": "2012-09-11T08:50:57.000Z",
  "title": "Flip Graphs of Degree-Bounded (Pseudo-)Triangulations",
  "authors": [
    "Oswin Aichholzer",
    "Thomas Hackl",
    "David Orden",
    "Pedro Ramos",
    "Günter Rote",
    "André Schulz",
    "Bettina Speckmann"
  ],
  "comment": "13 pages, 12 figures, acknowledgments updated",
  "categories": [
    "math.CO",
    "math.MG"
  ],
  "abstract": "We study flip 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 flip graph is connected if and only if $k > 6$; the diameter of the flip graph is $O(n^2)$. We also show that, for general point sets, flip graphs of pointed pseudo-triangulations can be disconnected for $k \\leq 9$, and flip 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 flip graph by a path of length $O(n \\log n)$, where every intermediate triangulation has maximum degree at most $k+4$.",
  "revisions": [
    {
      "version": "v5",
      "updated": "2012-09-11T08:50:57.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C62",
      "05C10",
      "52C99"
    ],
    "keywords": [
      "maximum degree",
      "study flip graphs",
      "convex point set",
      "maximum vertex degree",
      "general point sets"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 13,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2009arXiv0903.2184A"
    }
  }
}