×

zbMATH — the first resource for mathematics

A history of flips in combinatorial triangulations. (English) Zbl 1374.05067
Márquez, Alberto (ed.) et al., Computational geometry. XIV Spanish meeting on computational geometry, EGC 2011, dedicated to Ferran Hurtado on the occasion of his 60th birthday, Alcalá de Henares, Spain, June 27–30, 2011. Revised selected papers. Berlin: Springer (ISBN 978-3-642-34190-8/pbk). Lecture Notes in Computer Science 7579, 29-44 (2012).
Summary: Given two combinatorial triangulations, how many edge flips are necessary and sufficient to convert one into the other? This question has occupied researchers for over 75 years. We provide a comprehensive survey, including full proofs, of the various attempts to answer it.
For the entire collection see [Zbl 1253.68016].

MSC:
05C10 Planar graphs; geometric and topological aspects of graph theory
05-02 Research exposition (monographs, survey articles) pertaining to combinatorics
05-03 History of combinatorics
01A60 History of mathematics in the 20th century
01A61 History of mathematics in the 21st century
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aichholzer, O., Huemer, C., Krasser, H.: Triangulations without pointed spanning trees. Comput. Geom. 40(1), 79–83 (2008) · Zbl 1159.05304 · doi:10.1016/j.comgeo.2007.07.006
[2] Bose, P., Hurtado, F.: Flips in planar graphs. Comput. Geom. 42(1), 60–80 (2009) · Zbl 1146.05016 · doi:10.1016/j.comgeo.2008.04.001
[3] Bose, P., Jansens, D., van Renssen, A., Saumell, M., Verdonschot, S.: Making triangulations 4-connected using flips. In: Proceedings of the 23rd Canadian Conference on Computational Geometry, pp. 241–247 (2011); A full version of this paper can be found at arXiv:1110.6473
[4] Gao, Z., Urrutia, J., Wang, J.: Diagonal flips in labelled planar triangulations. Graphs Combin. 17(4), 647–657 (2001) · Zbl 0993.05058 · doi:10.1007/s003730170006
[5] Komuro, H.: The diagonal flips of triangulations on the sphere. Yokohama Math. J. 44(2), 115–122 (1997) · Zbl 0891.05020
[6] Mori, R., Nakamoto, A., Ota, K.: Diagonal flips in Hamiltonian triangulations on the sphere. Graphs Combin. 19(3), 413–418 (2003) · Zbl 1028.05025 · doi:10.1007/s00373-002-0508-6
[7] Negami, S., Nakamoto, A.: Diagonal transformations of graphs on closed surfaces. Sci. Rep. Yokohama Nat. Univ. Sect. I Math. Phys. Chem. 40, 71–97 (1993)
[8] Wagner, K.: Bemerkungen zum vierfarbenproblem. Jahresber. Dtsch. Math.-Ver. 46, 26–32 (1936) · JFM 62.0656.02
[9] Whitney, H.: A theorem on graphs. Ann. of Math. (2) 32(2), 378–390 (1931) · Zbl 0002.16101 · doi:10.2307/1968197
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.