Irreducible Triangulations of Surfaces with Boundary

A. Boulch, É. Colin de Verdière and A. Nakamoto

Graphs and Combinatorics, Springer Verlag, 2012

Paper HAL PDF

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 O(g + 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.

Citation

@article{boulch2013irreducible,
  title={Irreducible triangulations of surfaces with boundary},
  author={Boulch, Alexandre and Colin de Verdi{\`e}re, {\'E}ric and Nakamoto, Atsuhiro},
  journal={Graphs and Combinatorics},
  volume={29},
  number={6},
  pages={1675--1688},
  year={2013},
  publisher={Springer}
}