2 Search Results for "Delecroix, Vincent"

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}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2023.26

Algorithms for Length Spectra of Combinatorial Tori

Authors: Vincent Delecroix, Matthijs Ebbens, Francis Lazarus, and Ivan Yakovlev

Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)

Abstract

Consider a weighted, undirected graph cellularly embedded on a topological surface. The function assigning to each free homotopy class of closed curves the length of a shortest cycle within this homotopy class is called the marked length spectrum. The (unmarked) length spectrum is obtained by just listing the length values of the marked length spectrum in increasing order. In this paper, we describe algorithms for computing the (un)marked length spectra of graphs embedded on the torus. More specifically, we preprocess a weighted graph of complexity n in time O(n² log log n) so that, given a cycle with 𝓁 edges representing a free homotopy class, the length of a shortest homotopic cycle can be computed in O(𝓁+log n) time. Moreover, given any positive integer k, the first k values of its unmarked length spectrum can be computed in time O(k log n). Our algorithms are based on a correspondence between weighted graphs on the torus and polyhedral norms. In particular, we give a weight independent bound on the complexity of the unit ball of such norms. As an immediate consequence we can decide if two embedded weighted graphs have the same marked spectrum in polynomial time. We also consider the problem of comparing the unmarked spectra and provide a polynomial time algorithm in the unweighted case and a randomized polynomial time algorithm otherwise.

Cite as

Vincent Delecroix, Matthijs Ebbens, Francis Lazarus, and Ivan Yakovlev. Algorithms for Length Spectra of Combinatorial Tori. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 26:1-26:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{delecroix_et_al:LIPIcs.SoCG.2023.26,
  author =	{Delecroix, Vincent and Ebbens, Matthijs and Lazarus, Francis and Yakovlev, Ivan},
  title =	{{Algorithms for Length Spectra of Combinatorial Tori}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{26:1--26:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-273-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{258},
  editor =	{Chambers, Erin W. and Gudmundsson, Joachim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.26},
  URN =		{urn:nbn:de:0030-drops-178765},
  doi =		{10.4230/LIPIcs.SoCG.2023.26},
  annote =	{Keywords: graphs on surfaces, length spectrum, polyhedral norm}
}

Refine by Type
2 Document/PDF

Refine by Publication Year
1 2026
1 2023

Refine by Author
2 Delecroix, Vincent
1 Ebbens, Matthijs
1 Fontaine, Oscar
1 Lazarus, Francis
1 Yakovlev, Ivan
Show More...

Refine by Series/Journal
2 LIPIcs

Refine by Classification
2 Mathematics of computing → Graphs and surfaces
1 Mathematics of computing → Enumeration
1 Mathematics of computing → Geometric topology
1 Theory of computation → Computational geometry

Refine by Keyword
1 graphs on surfaces
1 irreducible triangulation
1 length spectrum
1 minimal position
1 polyhedral norm
Show More...

2 Search Results for "Delecroix, Vincent"

On the Size of k-Irreducible Triangulations

Abstract

Cite as

Algorithms for Length Spectra of Combinatorial Tori

Abstract

Cite as

Thanks for your feedback!

Could not send message