---
res:
  bibo_abstract:
  - How much cutting is needed to simplify the topology of a surface? We provide bounds
    for several instances of this question, for the minimum length of topologically
    non-trivial closed curves, pants decompositions, and cut graphs with a given combinatorial
    map in triangulated combinatorial surfaces (or their dual cross-metric counterpart).
    Our work builds upon Riemannian systolic inequalities, which bound the minimum
    length of non-trivial closed curves in terms of the genus and the area of the
    surface. We first describe a systematic way to translate Riemannian systolic inequalities
    to a discrete setting, and vice-versa. This implies a conjecture by Przytycka
    and Przytycki (Graph structure theory. Contemporary Mathematics, vol. 147, 1993),
    a number of new systolic inequalities in the discrete setting, and the fact that
    a theorem of Hutchinson on the edge-width of triangulated surfaces and Gromov’s
    systolic inequality for surfaces are essentially equivalent. We also discuss how
    these proofs generalize to higher dimensions. Then we focus on topological decompositions
    of surfaces. Relying on ideas of Buser, we prove the existence of pants decompositions
    of length O(g^(3/2)n^(1/2)) for any triangulated combinatorial surface of genus
    g with n triangles, and describe an O(gn)-time algorithm to compute such a decomposition.
    Finally, we consider the problem of embedding a cut graph (or more generally a
    cellular graph) with a given combinatorial map on a given surface. Using random
    triangulations, we prove (essentially) that, for any choice of a combinatorial
    map, there are some surfaces on which any cellular embedding with that combinatorial
    map has length superlinear in the number of triangles of the triangulated combinatorial
    surface. There is also a similar result for graphs embedded on polyhedral triangulations.@eng
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Éric
      foaf_name: Colin De Verdière, Éric
      foaf_surname: Colin De Verdière
  - foaf_Person:
      foaf_givenName: Alfredo
      foaf_name: Hubard, Alfredo
      foaf_surname: Hubard
  - foaf_Person:
      foaf_givenName: Arnaud N
      foaf_name: De Mesmay, Arnaud N
      foaf_surname: De Mesmay
      foaf_workInfoHomepage: http://www.librecat.org/personId=3DB2F25C-F248-11E8-B48F-1D18A9856A87
  bibo_doi: 10.1007/s00454-015-9679-9
  bibo_issue: '3'
  bibo_volume: 53
  dct_date: 2015^xs_gYear
  dct_identifier:
  - UT:000353895200006
  dct_language: eng
  dct_publisher: Springer@
  dct_title: Discrete systolic inequalities and decompositions of triangulated surfaces@
...