Flipping edge-labelled triangulations

DOI10.1016/J.COMGEO.2017.06.005MaRDI QIDQ1699301zbMATH OpenOpenAlexFDO

Authors Prosenjit Bose, Anna Lubiw, Vinayak Pathak, Sander Verdonschot

Publication date 19 February 2018

Published in Computational Geometry (Search for Journal in Brave)

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

zbMATH Keywords

flipconvex polygonquadrilateral graphsimultaneous flipspiral polygon

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Distance in graphs (05C12) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Lattices and convex bodies in (2) dimensions (aspects of discrete geometry) (52C05)

Abstract: Flips in triangulations have received a lot of attention over the past decades. However, the problem of tracking where particular edges go during the flipping process has not been addressed. We examine this question by attaching unique labels to the triangulation edges. We introduce the concept of the orbit of an edge $e$, which is the set of all edges reachable from $e$ via flips. We establish the first upper and lower bounds on the diameter of the flip graph in this setting. Specifically, we prove tight $Theta(nlogn)$ bounds for edge-labelled triangulations of $n$-vertex convex polygons and combinatorial triangulations, contrasting with the $Theta(n)$ bounds in their respective unlabelled settings. The $Omega(nlogn)$ lower bound for the convex polygon setting might be of independent interest, as it generalizes lower bounds on certain sorting models. When simultaneous flips are allowed, the upper bound for convex polygons decreases to $O(lo{g}^{2}n)$, although we no longer have a matching lower bound. Moving beyond convex polygons, we show that edge-labelled triangulated polygons with a single reflex vertex can have a disconnected flip graph. This is in sharp contrast with the unlabelled case, where the flip graph is connected for any triangulated polygon. For spiral polygons, we provide a complete characterization of the orbits. This allows us to decide connectivity of the flip graph of a spiral polygon in linear time. We also prove an upper bound of $O(n^2)$ on the diameter of each connected component, which is optimal in the worst case. We conclude with an example of a non-spiral polygon whose flip graph has diameter $Omega(n^3)$.

Recommendations

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

Cites work

• scientific article; zbMATH DE number 53528 (Why is no real title available?)
• scientific article; zbMATH DE number 3633698 (Why is no real title available?)
• scientific article; zbMATH DE number 1241392 (Why is no real title available?)
• A history of flips in combinatorial triangulations
• Arc diagrams, flip distances, and Hamiltonian triangulations
• Bounds for sorting by prefix reversal
• Colorful associahedra and cyclohedra
• Combinatorics of genome rearrangements.
• Efficient visibility queries in simple polygons
• Exact and approximation algorithms for sorting by reversals, with application to genome rearrangement
• Flipping edge-labelled triangulations
• Flipping edges in triangulations
• Flips in planar graphs
• Geometry and topology for mesh generation
• Improved bounds on sorting with length-weighted reversals
• Rotation Distance, Triangulations, and Hyperbolic Geometry
• SIMULTANEOUS EDGE FLIPPING IN TRIANGULATIONS
• Short Encodings of Evolving Structures
• The diameter of associahedra
• The edge rotation graph

Cited in

(23)

• A proof of the orbit conjecture for flipping edge-labelled triangulations
• Flipping in spirals
• scientific article; zbMATH DE number 1418487 (Why is no real title available?)
• A proof of the orbit conjecture for flipping edge-labelled triangulations
• Flipping edge-labelled triangulations
• Triangle-free triangulations
• Algorithms and Data Structures
• Eccentricities in the flip-graphs of convex polygons
• Connectivity of triangulation flip graphs in the plane
• Flip graphs of bounded degree triangulations
• Reconfiguring triangulations with edge flips and point moves
• Incremental topological flipping works for regular triangulations
• Flip graphs of bounded-degree triangulations
• Flip graphs, Yoke graphs and diameter
• Recoloring graphs of treewidth 2
• A polynomial version of Cereceda's conjecture
• scientific article; zbMATH DE number 7525461 (Why is no real title available?)
• Transforming plane triangulations by simultaneous diagonal flips
• Combinatorics. Abstracts from the workshop held January 1--7, 2023
• Convex dominating sets in maximal outerplanar graphs
• Flip Algorithm for Segment Triangulations
• Diagonal flips in labelled planar triangulations
• Flips in edge-labelled pseudo-triangulations

This page was built for publication: Flipping edge-labelled triangulations

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