Making triangulations 4-connected using flips (Q390117): Difference between revisions

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.