×

Clean triangulations. (English) Zbl 0741.05026

A surface \(S\) is a closed 2-manifold, either orientable \((S_p\), of genus \(p\geq 0)\) or nonorientable \((N_p\), of genus \(p>0\)). A clean triangulation of \(S\) is a 2-cell imbedding of a graph \(G\) into \(S\) having every 2-cell bounded by a 3-cycle of \(G\) and having every 3-cycle of \(G\) bound a 2-cell. Then \(\tau(S)\) denotes the smallest possible number of triangles in a clean triangulation of \(S\). For example, the tetrahedron shows that \(\tau(S_0)=4\). (The imbedding of \(K_3\) into \(S_0\) is not considered, as it does not correspond to a polyhedron.) The new results are: \(\tau(S_1)=24\), \(\tau(N_1)=20\), and (for \(p\to\infty)\) \(\lim \tau(S_p)/p=4\), \(\lim \tau(N_p)/p=2\). Thus \(\tau(S)\) has the same asymptotic behavior as \(\delta(S)\) (the smallest number of triangles in a (not necessarily clean) triangulation of \(S\)); see M. Jungerman and the second author [Acta Math. 145, 121–154 (1980; Zbl 0451.57005)] and the second author [Math. Ann. 130, 317–326 (1955; Zbl 0066.41702)].

MSC:

05C10 Planar graphs; geometric and topological aspects of graph theory
57M15 Relations of low-dimensional topology with graph theory
57N05 Topology of the Euclidean \(2\)-space, \(2\)-manifolds (MSC2010)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] G. A. Dirac: Map colour theorems.Canad. J. Math. 4 (1952), 480-490. · Zbl 0047.42203 · doi:10.4153/CJM-1952-043-9
[2] G. A. Dirac: Short proof of a map colour theorem.Canad. J. Math. 9 (1957), 225-226. · Zbl 0077.36802 · doi:10.4153/CJM-1957-027-2
[3] J. Edmonds: A combinatorial representation for polyhedral surfaces (abstract).Notices Amer. Math. Soc. 7 (1960), 646.
[4] M. Jungerman, andG. Ringel, Minimum triangulations on orientable surfaces.Acta Math. 145 (1980), 121-154. · Zbl 0451.57005 · doi:10.1007/BF02414187
[5] G. Ringel: Das Geschlecht des vollst?ndigen paaren Graphen.Abh. Math. Sem. Univ. Hamburg. 28 (1965), 139-150. · Zbl 0132.21203 · doi:10.1007/BF02993245
[6] G. Ringel: Wie man die geschlossenen nichtorientierbaren Fl?chen in m?glichst wenig Dreiecke zerlegen kann.Math. Ann. 130 (1955), 317-326. · Zbl 0066.41702 · doi:10.1007/BF01343898
[7] W. T. Tutte: A census of plane triangulations,Canad. J. Math. 14 (1962), 21-28. · Zbl 0103.39603 · doi:10.4153/CJM-1962-002-9
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.