---
_id: '5986'
abstract:
- lang: eng
text: "Given a triangulation of a point set in the plane, a flip deletes an edge
e whose removal leaves a convex quadrilateral, and replaces e by the opposite
diagonal of the quadrilateral. It is well known that any triangulation of a point
set can be reconfigured to any other triangulation by some sequence of flips.
We explore this question in the setting where each edge of a triangulation has
a label, and a flip transfers the label of the removed edge to the new edge. It
is not true that every labelled triangulation of a point set can be reconfigured
to every other labelled triangulation via a sequence of flips, but we characterize
when this is possible. There is an obvious necessary condition: for each label
l, if edge e has label l in the first triangulation and edge f has label l in
the second triangulation, then there must be some sequence of flips that moves
label l from e to f, ignoring all other labels. Bose, Lubiw, Pathak and Verdonschot
formulated the Orbit Conjecture, which states that this necessary condition is
also sufficient, i.e. that all labels can be simultaneously mapped to their destination
if and only if each label individually can be mapped to its destination. We prove
this conjecture. Furthermore, we give a polynomial-time algorithm (with \U0001D442(\U0001D45B8)
being a crude bound on the run-time) to find a sequence of flips to reconfigure
one labelled triangulation to another, if such a sequence exists, and we prove
an upper bound of \U0001D442(\U0001D45B7) on the length of the flip sequence.
Our proof uses the topological result that the sets of pairwise non-crossing edges
on a planar point set form a simplicial complex that is homeomorphic to a high-dimensional
ball (this follows from a result of Orden and Santos; we give a different proof
based on a shelling argument). The dual cell complex of this simplicial ball,
called the flip complex, has the usual flip graph as its 1-skeleton. We use properties
of the 2-skeleton of the flip complex to prove the Orbit Conjecture."
article_processing_charge: Yes (via OA deal)
article_type: original
author:
- first_name: Anna
full_name: Lubiw, Anna
last_name: Lubiw
- first_name: Zuzana
full_name: Masárová, Zuzana
id: 45CFE238-F248-11E8-B48F-1D18A9856A87
last_name: Masárová
orcid: 0000-0002-6660-1322
- first_name: Uli
full_name: Wagner, Uli
id: 36690CA2-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
orcid: 0000-0002-1494-0568
citation:
ama: Lubiw A, Masárová Z, Wagner U. A proof of the orbit conjecture for flipping
edge-labelled triangulations. *Discrete & Computational Geometry*. 2019;61(4):880-898.
doi:10.1007/s00454-018-0035-8
apa: Lubiw, A., Masárová, Z., & Wagner, U. (2019). A proof of the orbit conjecture
for flipping edge-labelled triangulations. *Discrete & Computational Geometry*.
Springer Nature. https://doi.org/10.1007/s00454-018-0035-8
chicago: Lubiw, Anna, Zuzana Masárová, and Uli Wagner. “A Proof of the Orbit Conjecture
for Flipping Edge-Labelled Triangulations.” *Discrete & Computational Geometry*.
Springer Nature, 2019. https://doi.org/10.1007/s00454-018-0035-8.
ieee: A. Lubiw, Z. Masárová, and U. Wagner, “A proof of the orbit conjecture for
flipping edge-labelled triangulations,” *Discrete & Computational Geometry*,
vol. 61, no. 4. Springer Nature, pp. 880–898, 2019.
ista: Lubiw A, Masárová Z, Wagner U. 2019. A proof of the orbit conjecture for flipping
edge-labelled triangulations. Discrete & Computational Geometry. 61(4), 880–898.
mla: Lubiw, Anna, et al. “A Proof of the Orbit Conjecture for Flipping Edge-Labelled
Triangulations.” *Discrete & Computational Geometry*, vol. 61, no. 4,
Springer Nature, 2019, pp. 880–98, doi:10.1007/s00454-018-0035-8.
short: A. Lubiw, Z. Masárová, U. Wagner, Discrete & Computational Geometry 61
(2019) 880–898.
corr_author: '1'
date_created: 2019-02-14T11:54:08Z
date_published: 2019-06-01T00:00:00Z
date_updated: 2024-10-09T20:59:36Z
day: '01'
ddc:
- '000'
department:
- _id: UlWa
doi: 10.1007/s00454-018-0035-8
external_id:
arxiv:
- '1710.02741'
isi:
- '000466130000009'
file:
- access_level: open_access
checksum: e1bff88f1d77001b53b78c485ce048d7
content_type: application/pdf
creator: dernst
date_created: 2019-02-14T11:57:22Z
date_updated: 2020-07-14T12:47:14Z
file_id: '5988'
file_name: 2018_DiscreteGeometry_Lubiw.pdf
file_size: 556276
relation: main_file
file_date_updated: 2020-07-14T12:47:14Z
has_accepted_license: '1'
intvolume: ' 61'
isi: 1
issue: '4'
language:
- iso: eng
license: https://creativecommons.org/licenses/by/4.0/
month: '06'
oa: 1
oa_version: Published Version
page: 880-898
project:
- _id: B67AFEDC-15C9-11EA-A837-991A96BB2854
name: IST Austria Open Access Fund
publication: Discrete & Computational Geometry
publication_identifier:
eissn:
- 1432-0444
issn:
- 0179-5376
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '683'
relation: earlier_version
status: public
- id: '7944'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: A proof of the orbit conjecture for flipping edge-labelled triangulations
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 61
year: '2019'
...