Article in volume
Authors:
Title:
Flippable edges in triangulations on surfaces
PDFSource:
Discussiones Mathematicae Graph Theory 42(4) (2022) 1041-1059
Received: 2019-12-19 , Revised: 2020-04-25 , Accepted: 2020-04-25 , Available online: 2020-11-21 , https://doi.org/10.7151/dmgt.2377
Abstract:
Concerning diagonal flips on triangulations, Gao et al. showed that any
triangulation $G$ on the sphere with $n \ge 5$ vertices has at least $n-2$
flippable edges. Furthermore, if $G$ has minimum degree at least 4 and $n\ge 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
References:
- 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 - D.W. Barnette and A.L. Edelson, All $2$-manifolds have finitely many minimal trian-
gulations, Israel J. Math. 67 (1989) 123–128.
https://doi.org/10.1007/BF02764905 - A. Boulch, É. Colin de Verdière and A. Nakamoto, Irreducible triangulations of sur-
faces with boundary, Graphs Combin. 29 (2013) 1675–1688.
https://doi.org/10.1007/s00373-012-1244-1 - 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 - 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 - Z. Gao, L.B. Richmond and C. Thomassen, Irreducible triangulations and triangular embeddings on a surface, CORR 91-07, University of Waterloo.
- 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 - 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 - 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 - S. Lawrencenko, The irreducible triangulations of the torus, Ukrain. Geom. Sb. 30 (1987) 52–62.
- 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 - 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 - 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 - S. Negami, Diagonal flips in triangulations of surfaces, Discrete Math. 135 (1994) 225–232.
https://doi.org/10.1016/0012-365X(93)E0101-9 - 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 - 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 - E. Steinitz and H. Rademacher, Vorlesungen über die Theoric der Polyeder (Springer, Berlin, 1934).
- 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 - T. Sulanke, Generating irreducible triangulations of surfaces, preprint.
- K. Wagner, Bemerkungen zum Vierfarbenproblem, J. der Deut. Math. Ver. 46, Abt. 1 (1936) 26–32.
Close