DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2022): 0.7

5-year Journal Impact Factor (2022): 0.7

CiteScore (2022): 1.9

SNIP (2022): 0.902

Discussiones Mathematicae Graph Theory

Article in volume


Authors:

D. Ikegami

Daiki Ikegami

Graduate School of Environment and Information Science, Yokohama National University

email: ikegami-daiki-xj@ynu.jp

A. Nakamoto

Atsuhiro Nakamoto

email: nakamoto@ynu.ac.jp

Title:

Flippable edges in triangulations on surfaces

PDF

Source:

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:

  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 trian-
    gulations
    , 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 sur-
    faces 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.

Close