Making triangulations 4-connected using flips
type: Item
instance of: scholarly article
title: Making triangulations 4-connected using flips
zbMATH Open document ID: 1312.65019
author: Prosenjit Bose
author: Dana Jansens
author: André van Renssen
author: Maria Saumell
author: Sander Verdonschot
published in: Computational Geometry
publication date: 2014-01-22T00:00:00Z
full work available at URL: https://arxiv.org/abs/1110.6473
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.
reviewed by: H. P. Dikshit
Mathematics Subject Classification ID: 65D18
Mathematics Subject Classification ID: 05C40
zbMATH DE Number: 6249143
zbMATH Keywords: diagonal flip
zbMATH Keywords: flip graph
zbMATH Keywords: triangulation
zbMATH Keywords: 4-connected triangulation
zbMATH Keywords: Hamiltonian triangulation
MaRDI profile type: Publication
OpenAlex ID: W2161217328
arXiv ID: 1110.6473
cites work: A History of Flips in Combinatorial Triangulations
cites work: Flips in planar graphs
cites work: Bemerkungen zum Vierfarbenproblem
cites work: Q4351464
cites work: Diagonal flips in Hamiltonian triangulations on the sphere
cites work: A theorem on graphs
cites work: Simultaneous diagonal flips in plane triangulations
cites work: Triangulations without pointed spanning trees
DOI: 10.1016/J.COMGEO.2012.10.012
description: scientific article; zbMATH DE number 6249143