Geodesic
Flippable Edges in Triangulations on Surfaces
Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 4, pp. 1041-1059.

Voir la notice de l'article provenant de la source Library of Science

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: triangulation, diagonal flip, surface 
@article{DMGT_2022_42_4_a1,
     author = {Ikegami, Daiki and Nakamoto, Atsuhiro},
     title = {Flippable {Edges} in {Triangulations} on {Surfaces}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {1041--1059},
     publisher = {mathdoc},
     volume = {42},
     number = {4},
     year = {2022},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2022_42_4_a1/}
}
TY  - JOUR
AU  - Ikegami, Daiki
AU  - Nakamoto, Atsuhiro
TI  - Flippable Edges in Triangulations on Surfaces
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2022
SP  - 1041
EP  - 1059
VL  - 42
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2022_42_4_a1/
LA  - en
ID  - DMGT_2022_42_4_a1
ER  - 
%0 Journal Article
%A Ikegami, Daiki
%A Nakamoto, Atsuhiro
%T Flippable Edges in Triangulations on Surfaces
%J Discussiones Mathematicae. Graph Theory
%D 2022
%P 1041-1059
%V 42
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2022_42_4_a1/
%G en
%F DMGT_2022_42_4_a1
Ikegami, Daiki; Nakamoto, Atsuhiro. Flippable Edges in Triangulations on Surfaces. Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 4, pp. 1041-1059. http://geodesic.mathdoc.fr/item/DMGT_2022_42_4_a1/

[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-7

[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/BF02764905

[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-1

[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.0070

[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-9

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

[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/s003730170006

[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.004

[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.1889

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

[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.1920

[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-6

[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-0

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

[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.3190200211

[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/1496161326

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

[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.001

[19] T. Sulanke, Generating irreducible triangulations of surfaces, preprint.

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