{
  "id": "math/0509478",
  "version": "v2",
  "published": "2005-09-21T12:45:55.000Z",
  "updated": "2006-04-26T10:17:53.000Z",
  "title": "Simultaneous Diagonal Flips in Plane Triangulations",
  "authors": [
    "Prosenjit Bose",
    "Jurek Czyzowicz",
    "Zhicheng Gao",
    "Pat Morin",
    "David R. Wood"
  ],
  "comment": "A short version of this paper will be presented at SODA 2006",
  "journal": "J. Graph Theory 54(4):307-330, 2007",
  "doi": "10.1002/jgt.20214",
  "categories": [
    "math.CO",
    "cs.CG"
  ],
  "abstract": "Simultaneous diagonal flips in plane triangulations are investigated. It is proved that every $n$-vertex triangulation with at least six vertices has a simultaneous flip into a 4-connected triangulation, and that it can be computed in O(n) time. It follows that every triangulation has a simultaneous flip into a Hamiltonian triangulation. This result is used to prove that for any two $n$-vertex triangulations, there exists a sequence of $O(\\log n)$ simultaneous flips to transform one into the other. The total number of edges flipped in this sequence is O(n). The maximum size of a simultaneous flip is then studied. It is proved that every triangulation has a simultaneous flip of at least ${1/3}(n-2)$ edges. On the other hand, every simultaneous flip has at most $n-2$ edges, and there exist triangulations with a maximum simultaneous flip of ${6/7}(n-2)$ edges.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2006-04-26T10:17:53.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C10"
    ],
    "keywords": [
      "simultaneous diagonal flips",
      "plane triangulations",
      "vertex triangulation",
      "maximum simultaneous flip",
      "hamiltonian triangulation"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2005math......9478B"
    }
  }
}