Making triangulations 4-connected using flips

DOI10.1016/J.COMGEO.2012.10.012MaRDI QIDQ390117zbMATH OpenOpenAlexFDO

Authors Prosenjit Bose, Dana Jansens, André van Renssen, Maria Saumell, Sander Verdonschot

Publication date 22 January 2014

Published in Computational Geometry (Search for Journal in Brave)

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

zbMATH Keywords

triangulationflip graph4-connected triangulationdiagonal flipHamiltonian triangulation

Mathematics Subject Classification ID

Connectivity (05C40) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Abstract: We show that any combinatorial triangulation on n vertices can be transformed into a 4-connected one using at most floor((3n - 9)/5) edge flips. We also give an example of an infinite family of triangulations that requires this many flips to be made 4-connected, showing that our bound is tight. In addition, for n >= 19, we improve the upper bound on the number of flips required to transform any 4-connected triangulation into the canonical triangulation (the triangulation with two dominant vertices), matching the known lower bound of 2n - 15. Our results imply a new upper bound on the diameter of the flip graph of 5.2n - 33.6, improving on the previous best known bound of 6n - 30.

Recommendations

• Flip graphs of bounded-degree triangulations
• Flip graphs of bounded degree triangulations
• Diagonal flips in plane graphs with triangular and quadrangular faces
• Arc diagrams, flip distances, and Hamiltonian triangulations
• Arc diagrams, flip distances, and Hamiltonian triangulations

Cites work

• scientific article; zbMATH DE number 1053457 (Why is no real title available?)
• A history of flips in combinatorial triangulations
• A theorem on graphs
• Bemerkungen zum Vierfarbenproblem
• Diagonal flips in Hamiltonian triangulations on the sphere
• Flips in planar graphs
• Triangulations without pointed spanning trees

Cited in

(12)

• Flipping in spirals
• Arc diagrams, flip distances, and Hamiltonian triangulations
• Flip graphs of stacked and flag triangulations of the 2-sphere
• Flip graphs of bounded degree triangulations
• Diagonal flips in plane graphs with triangular and quadrangular faces
• Flip graphs of bounded-degree triangulations
• The flip-graph of the 4-dimensional cube is connected
• On signed diagonal flip sequences
• Transforming plane triangulations by simultaneous diagonal flips
• Flips in combinatorial pointed pseudo-triangulations with face degree at most four
• Arc diagrams, flip distances, and Hamiltonian triangulations
• A lower bound on the diameter of the flip graph

This page was built for publication: Making triangulations 4-connected using flips

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