×

Irreducible triangulations of surfaces. (English) Zbl 0863.05029

The authors show that, for any surface \(S\) and any \(k\), there are at most finitely many triangulations of \(S\) such that each edge is in a noncontractible cycle of length \(k\), but is in no shorter noncontractible cycle; such a triangulation is said to be \(k\)-irreducible. If \(S\) is the sphere with \(h\) handles (respectively the sphere with \(k\) crosscaps), then the Euler genus of \(S\) is \(2h\) (respectively \(k)\). Specifically, the authors show that if \(T\) is a \(k\)-irreducible triangulation of \(S\), of Euler genus \(g\), and if \(k\geq 2\), then \(|E(T)|\leq 3k\) \(k!(6k)^kg^2\).

MSC:

05C10 Planar graphs; geometric and topological aspects of graph theory
PDFBibTeX XMLCite
Full Text: DOI