Irreducible Triangulations of Surfaces with BoundaryReport as inadecuate

Irreducible Triangulations of Surfaces with Boundary - Download this document for free, or read online. Document in PDF available to download.

1 Ecole Polytechnique Palaiseau 2 DI-ENS - Département d-informatique de l-École normale supérieure 3 Yokohama National University, Yokohama 240-8501, Japan

Abstract : A triangulation of a surface is irreducible if no edge can be contracted to produce a triangulation of the same surface. In this paper, we investigate irreducible triangulations of surfaces with boundary. We prove that the number of vertices of an irreducible triangulation of a possibly non-orientable surface of genus g ≥ 0 with b ≥ 0 boundary components is Og + b. So far, the result was known only for surfaces without boundary b = 0. While our technique yields a worse constant in the O. notation, the present proof is elementary, and simpler than the previous ones in the case of surfaces without boundary.

Author: Alexandre Boulch - Éric Colin de Verdière - Atsuhiro Nakamoto -



Related documents