1. bookVolume 42 (2022): Issue 4 (November 2022)
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

Flippable Edges in Triangulations on Surfaces

Published Online: 12 Jul 2022
Volume & Issue: Volume 42 (2022) - Issue 4 (November 2022)
Page range: 1041 - 1059
Received: 19 Dec 2019
Accepted: 25 Apr 2020
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
Abstract

Concerning diagonal flips on triangulations, Gao et al. showed that any triangulation G on the sphere with n ≥ 5 vertices has at least n − 2 flippable edges. Furthermore, if G has minimum degree at least 4 and n ≥ 9, then G has at least 2n + 3 flippable edges. In this paper, we give a simpler proof of their results, and extend them to the case of the projective plane, the torus and the Klein bottle. Finally, we give an estimation for the number of flippable edges of a triangulation on general surfaces, using the notion of irreducible triangulations.

Keywords

MSC 2010

[1] D. Barnette, Generating the triangulations of the projective plane, J. Combin. Theory Ser. B 33 (1982) 222–230. https://doi.org/10.1016/0095-8956(82)90041-7Search in Google Scholar

[2] D.W. Barnette and A.L. Edelson, All 2-manifolds have finitely many minimal triangulations, Israel J. Math. 67 (1989) 123–128. https://doi.org/10.1007/BF02764905Search in Google Scholar

[3] A. Boulch, É. Colin de Verdière and A. Nakamoto, Irreducible triangulations of surfaces with boundary, Graphs Combin. 29 (2013) 1675–1688. https://doi.org/10.1007/s00373-012-1244-1Search in Google Scholar

[4] R. Brunet, A. Nakamoto and S. Negami, Diagonal flips of triangulations on closed surfaces preserving specified properties, J. Combin. Theory Ser. B 68 (1996) 295–309. https://doi.org/10.1006/jctb.1996.0070Search in Google Scholar

[5] A.K. Dewdney, Wagner’s theorem for torus graphs, Discrete Math. 4 (1973) 139–149. https://doi.org/10.1016/0012-365X(73)90076-9Search in Google Scholar

[6] Z. Gao, L.B. Richmond and C. Thomassen, Irreducible triangulations and triangular embeddings on a surface, CORR 91-07, University of Waterloo.Search in Google Scholar

[7] Z. Gao, J. Urrutia and J. Wang, Diagonal flips in labelled planar triangulations, Graphs Combin. 17 (2001) 647–657. https://doi.org/10.1007/s003730170006Search in Google Scholar

[8] G. Joret and D.R. Wood, Irreducible triangulations are small, J. Combin. Theory Ser. B 100 (2010) 446–455. https://doi.org/10.1016/j.jctb.2010.01.004Search in Google Scholar

[9] H. Komuro, A. Nakamoto and S. Negami, Diagonal flips in triangulations on closed surfaces with minimum degree at least 4, J. Combin. Theory Ser. B 76 (1999) 68–92. https://doi.org/10.1006/jctb.1998.1889Search in Google Scholar

[10] S. Lawrencenko, The irreducible triangulations of the torus, Ukrain. Geom. Sb. 30 (1987) 52–62.Search in Google Scholar

[11] S. Lawrencenko and S. Negami,, Constructing the graphs that triangulate both the torus and the Klein Bottle, J. Combin. Theory Ser. B 77 (1999) 211–218. https://doi.org/10.1006/jctb.1999.1920Search in Google Scholar

[12] R. Mori, A. Nakamoto and K. Ota, Diagonal flips in Hamiltonian triangulations on the sphere, Graphs Combin. 19 (2003) 413–418. https://doi.org/10.1007/s00373-002-0508-6Search in Google Scholar

[13] A. Nakamoto and S. Negami, Generating triangulations on closed surfaces with minimum degree at least 4, Discrete Math. 244 (2002) 345–349. https://doi.org/10.1016/S0012-365X(01)00093-0Search in Google Scholar

[14] S. Negami, Diagonal flips in triangulations of surfaces, Discrete Math. 135 (1994) 225-232. https://doi.org/10.1016/0012-365X(93)E0101-9Search in Google Scholar

[15] A. Nakamoto and K. Ota, Note on irreducible triangulations of surfaces, J. Graph Theory 20 (1995) 227–233. https://doi.org/10.1002/jgt.3190200211Search in Google Scholar

[16] S. Negami and S. Watanabe, Diagonal transformations of triangulations on surfaces, Tsukuba J. Math. 14 (1990) 155–166. https://doi.org/10.21099/tkbjm/1496161326Search in Google Scholar

[17] E. Steinitz and H. Rademacher, Vorlesungen über die Theoric der Polyeder (Springer, Berlin, 1934).Search in Google Scholar

[18] T. Sulanke, Note on the irreducible triangulations of the Klein bottle, J. Combin. Theory Ser. B 96 (2006) 964–972. https://doi.org/10.1016/j.jctb.2006.05.001Search in Google Scholar

[19] T. Sulanke, Generating irreducible triangulations of surfaces, preprint.Search in Google Scholar

[20] K. Wagner, Bemerkungen zum Vierfarbenproblem, J. der Deut. Math. Ver. 46, Abt. 1 (1936) 26–32.Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo