2026-07-21T19:27:54Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25844 2026-06-23T12:59:24Z ddc:004 open_access

On the Size of k-Irreducible Triangulations Delecroix, Vincent Fontaine, Oscar de Mesmay, Arnaud surface irreducible triangulation system of curves minimal position systolic geometry 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]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Vincent Delecroix and Oscar Fontaine and Arnaud de Mesmay 2026 Is Part Of LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2026.38 urn:nbn:de:0030-drops-258446 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.38 eng https://creativecommons.org/licenses/by/4.0/legalcode