DROPS

Document

DOI: 10.4230/LIPIcs.SoCG.2026.38

On the Size of k-Irreducible Triangulations

Authors: Vincent Delecroix, Oscar Fontaine, and Arnaud de Mesmay

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract

A triangulation of a surface is k-irreducible if every non-contractible curve has length at least k and any edge contraction breaks this property. Equivalently, every edge belongs to a non-contractible curve of length k and there are no shorter non-contractible curves. We prove that a k-irreducible triangulation of an orientable surface of genus g has O(k²g) triangles, which is optimal. This is an improvement over the previous best bound k^O(k) g² of Gao, Richter and Seymour [Journal of Combinatorial Theory, Series B, 1996].

Cite as

Vincent Delecroix, Oscar Fontaine, and Arnaud de Mesmay. On the Size of k-Irreducible Triangulations. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 38:1-38:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{delecroix_et_al:LIPIcs.SoCG.2026.38,
  author =	{Delecroix, Vincent and Fontaine, Oscar and de Mesmay, Arnaud},
  title =	{{On the Size of k-Irreducible Triangulations}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{38:1--38:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.38},
  URN =		{urn:nbn:de:0030-drops-258446},
  doi =		{10.4230/LIPIcs.SoCG.2026.38},
  annote =	{Keywords: surface, irreducible triangulation, system of curves, minimal position, systolic geometry}
}

Search Results

Documents authored by Fontaine, Oscar

On the Size of k-Irreducible Triangulations

Abstract

Cite as

Thanks for your feedback!

Could not send message