×

Constructing the graphs that triangulate both the torus and the Klein bottle. (English) Zbl 1025.05018

We establish a method to construct all the graphs that can be embedded on both the torus and the Klein bottle as their triangulations. More concretely, every such graph can be obtained from a unique irreducible triangulation on the torus or on the Klein bottle with some of its faces subdivided into several triangles suitably.

MSC:

05C10 Planar graphs; geometric and topological aspects of graph theory
57M99 General low-dimensional topology
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Barnette, D. W., Generating the triangulations of the projective plane, J. Combin. Theory Ser. B, 33, 222-230 (1982) · Zbl 0509.52007
[2] Barnette, D. W., Generating closed 2-cell embeddings in the torus and the projective plane, Discrete Comput. Geom., 2, 233-247 (1987) · Zbl 0614.51008
[3] Barnette, D. W., Generating the 4-connected and strongly 4-connected triangulations on the torus and projective plane, Discrete Math., 85, 1-16 (1990) · Zbl 0728.05018
[4] Barnette, D. W., Generating projective plane polyhedral maps, J. Combin. Theory Ser. B, 51, 277-291 (1991) · Zbl 0722.05029
[5] Barnette, D. W.; Edelson, A. L., All 2-manifolds have finitely many minimal triangulations, Israel J. Math., 67, 123-128 (1989) · Zbl 0689.57008
[6] Franklin, P., A six colour problem, J. Math. Phys., 13, 363-369 (1934) · JFM 60.0501.04
[7] Gao, Z.; Richter, R. B.; Seymour, P. D., Irreducible triangulations of surfaces, J. Combin. Theory Ser. B, 68, 206-217 (1996) · Zbl 0863.05029
[8] Lawrencenko, S., Irreducible triangulations of the torus, Ukrain. Geom. Sb., 30, 52-62 (1987) · Zbl 0629.57013
[9] Lawrencenko, S.; Negami, S., Irreducible triangulations of the Klein bottle, J. Combin. Theory Ser. B, 70, 265-291 (1997) · Zbl 0876.05023
[10] Malnic, A.; Mohar, B., Generating locally cyclic triangulations of surfaces, J. Combin. Theory Ser. B, 56, 147-164 (1992) · Zbl 0723.05053
[11] Malnic, A.; Nedela, R., \(k\)-minimal triangulations of surfaces, Acta Math. Univ. Comenian. (N.S.), 64, 57-76 (1995) · Zbl 0921.05029
[12] Mohar, B., Nonorientable genus of nearly complete bipartite graphs, Discrete Comput. Geom., 3, 137-146 (1988) · Zbl 0628.05026
[13] Nakamoto, A.; Ota, K., Note on irreducible triangulations of surfaces, J. Graph Theory, 20, 227-233 (1995) · Zbl 0834.05021
[14] Negami, S., Diagonal flips in triangulations of surfaces, Discrete Math., 135, 225-232 (1994) · Zbl 0823.05028
[15] Ringel, G., Wie man die geschlossenen nichtorientierbaren Flächen in möglichst wenig Dreiecke zerlegen kann, Math. Ann., 130, 317-326 (1955) · Zbl 0066.41702
[16] Ringel, G., Minimal triangulations of orientable surfaces, Acta Math., 145, 121-154 (1980) · Zbl 0451.57005
[17] White, A. T., Graphs, Groups and Surfaces (1984), North-Holland: North-Holland Amsterdam · Zbl 0378.05028
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.