A proof of the orbit conjecture for flipping edge-labelled triangulations

DOI10.4230/LIPICS.SOCG.2017.49zbMATH Open1432.05093arXiv1710.02741OpenAlexW2948460206MaRDI QIDQ4580126FDOQ4580126

Authors: Anna Lubiw, Zuzana Masárová, Uli Wagner 

Publication date: 13 August 2018

Abstract: Given a triangulation of a point set in the plane, a emph{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. We characterize when this is possible by proving the emph{Orbit Conjecture} of Bose, Lubiw, Pathak and Verdonschot which states that emph{all} labels can be simultaneously mapped to their destination if and only if emph{each} label individually can be mapped to its destination. Furthermore, we give a polynomial-time algorithm 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 $O(n^7)$ 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 emph{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.

Full work available at URL: https://arxiv.org/abs/1710.02741

Recommendations

• A proof of the orbit conjecture for flipping edge-labelled triangulations
• Flipping edge-labelled triangulations
• Flipping edges in triangulations
• SIMULTANEOUS EDGE FLIPPING IN TRIANGULATIONS
• Flips in edge-labelled pseudo-triangulations

zbMATH Keywords

fliptriangulationsDelaunay triangulationreconfigurationshellabilityconstrained triangulationspiecewise linear balls

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Arrangements of points, flats, hyperplanes (aspects of discrete geometry) (52C35)

Cited In (9)

• A proof of the orbit conjecture for flipping edge-labelled triangulations
• Flipping edge-labelled triangulations
• Introduction to reconfiguration
• All triangulations are reachable via sequences of edge-flips: an elementary proof
• Triangulations without pointed spanning trees
• Flips signés et triangulations d'un polygone. (Signed flips and triangulations of a polygon)
• Reconfiguration of graph minors
• Simultaneously flippable edges in triangulations
• Convex dominating sets in maximal outerplanar graphs

This page was built for publication: A proof of the orbit conjecture for flipping edge-labelled triangulations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4580126)