Flipping edge-labelled triangulations

DOI10.1016/J.COMGEO.2017.06.005zbMATH Open1380.05173arXiv1310.1166OpenAlexW2963273558MaRDI QIDQ1699301FDOQ1699301

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

Publication date: 19 February 2018

Published in: Computational Geometry (Search for Journal in Brave)

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)$.

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

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

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)

Cites Work

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

Cited In (24)

• Flipping in spirals
• Title not available (Why is that?)
• Transition operations over plane trees
• 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
• Incremental topological flipping works for regular triangulations
• Reconfiguring triangulations with edge flips and point moves
• Flip graphs of bounded-degree triangulations
• Flip graphs, Yoke graphs and diameter
• Recoloring graphs of treewidth 2
• Title not available (Why is that?)
• A polynomial version of Cereceda's conjecture
• Transforming plane triangulations by simultaneous diagonal flips
• Combinatorics. Abstracts from the workshop held January 1--7, 2023
• Convex dominating sets in maximal outerplanar graphs
• Diagonal flips in labelled planar triangulations
• Flip Algorithm for Segment Triangulations
• Flips in edge-labelled pseudo-triangulations
• A proof of the orbit conjecture for flipping edge-labelled 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)