Flippable Edges in Triangulations on Surfaces
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...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
University of Zielona Góra
2022-11-01
|
| Series: | Discussiones Mathematicae Graph Theory |
| Subjects: | |
| Online Access: | https://doi.org/10.7151/dmgt.2377 |
| _version_ | 1797725545823207424 |
|---|---|
| author | Ikegami Daiki Nakamoto Atsuhiro |
| author_facet | Ikegami Daiki Nakamoto Atsuhiro |
| author_sort | Ikegami Daiki |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-03-12T10:32:48Z |
| format | Article |
| id | doaj.art-812ca840e3ec4987832f18f749841add |
| institution | Directory Open Access Journal |
| issn | 2083-5892 |
| language | English |
| last_indexed | 2024-03-12T10:32:48Z |
| publishDate | 2022-11-01 |
| publisher | University of Zielona Góra |
| record_format | Article |
| series | Discussiones Mathematicae Graph Theory |
| spelling | doaj.art-812ca840e3ec4987832f18f749841add2023-09-02T09:07:26ZengUniversity of Zielona GóraDiscussiones Mathematicae Graph Theory2083-58922022-11-014241041105910.7151/dmgt.2377Flippable Edges in Triangulations on SurfacesIkegami Daiki0Nakamoto Atsuhiro1Graduate School of Environment and Information Science, Yokohama National University, 79-7 Tokiwadai, Hodogaya-ku, Yokohama240-8501, JapanFaculty of Environment and Information Science, Yokohama National University, 79-7 Tokiwadai, Hodogaya-ku, Yokohama240-8501, JapanConcerning 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.https://doi.org/10.7151/dmgt.2377triangulationdiagonal flipsurface05c10 |
| spellingShingle | Ikegami Daiki Nakamoto Atsuhiro Flippable Edges in Triangulations on Surfaces Discussiones Mathematicae Graph Theory triangulation diagonal flip surface 05c10 |
| title | Flippable Edges in Triangulations on Surfaces |
| title_full | Flippable Edges in Triangulations on Surfaces |
| title_fullStr | Flippable Edges in Triangulations on Surfaces |
| title_full_unstemmed | Flippable Edges in Triangulations on Surfaces |
| title_short | Flippable Edges in Triangulations on Surfaces |
| title_sort | flippable edges in triangulations on surfaces |
| topic | triangulation diagonal flip surface 05c10 |
| url | https://doi.org/10.7151/dmgt.2377 |
| work_keys_str_mv | AT ikegamidaiki flippableedgesintriangulationsonsurfaces AT nakamotoatsuhiro flippableedgesintriangulationsonsurfaces |