The paper by Vincent Delecroix and Oscar Fontaine, in collaboration with Arnaud de Mesmay (LIGM Marne-la-Vallée), accepted at SoCG (Symposium on Computational Geometry), received the Best Theory Paper Award. Title of the paper: “On the size of k-irreducible triangulations.”
Oscar Fontaine presented the paper at the conference (June 2–5, 2026), which took place in New Brunswick (USA).
Surface triangulations are combinatorial objects used to represent topological spaces. Specifically, they consist of a set of triangles joined in pairs along their sides to form a topological surface. In this article, the authors focus on particularly rigid triangulations: k-irreducible triangulations. These are defined by two properties: every non-contractible curve has length at least k, and any edge contraction violates this property. The main result is an optimal upper bound (up to a multiplicative factor) on the size of such a triangulation. This bound is a significant improvement over the previous known bound, which dates back 30 years and was established by Gao, Richter, and Seymour.
Read the article here.