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

4-connected triangulationdiagonal flipflip graphHamiltonian triangulationtriangulation

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.

Review text

Studying the problem of making triangulations 4-connected in the setting where many edges may be flipped simultaneously, \textit{P. Bose} et al. [J. Graph Theory 54, No. 4, 307--330 (2007; Zbl 1120.05024)] have shown that any triangulation can be made 4-connected by one simultaneous flip. Improving the first step of the construction by \textit{R. Mori} et al. [Graphs Comb. 19, No. 3, 413--418 (2003; Zbl 1028.05025)], the authors show that any triangulation can be made 4-connected using at most \([(3n-9)/5]\) flips. For \(n \geq 19\), the authors also improve the bound on the second step of their algorithm (cf. [\textit{H. Komuro}, Yokohama Math. J. 44, No. 2, 115--122 (1997; Zbl 0891.05020)]). It is also shown that if \(n\) is a multiple 5, there are triangulations that require \( (3n-10)/5 \) flips to be made 4-connected.

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

• 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
• scientific article; zbMATH DE number 1053457 (Why is no real title available?)
• Triangulations without pointed spanning trees

Cited in

(13)

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

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)