Author(s): | Colin de Verdière, Éric; Hubard, Alfredo; de Mesmay, Arnaud |

Article Title: | Discrete systolic inequalities and decompositions of triangulated surfaces |

Affiliation | IST Austria |

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

Keywords: | Systole; Edge-width; Surface; Closed curve; Cut graph; Pants decomposition |

Journal Title: | Discrete & Computational Geometry |

Volume: | 53 |

Issue | 3 |

ISSN: | 0179-5376 |

Publisher: | Springer |

Date Published: | 2015-04-02 |

Start Page: | 587 |

End Page: | 620 |

Sponsor: | This work was supported by the French ANR Blanc Project ANR-12-BS02-005 (RDAM). |

URL: | |

DOI: | 10.1007/s00454-015-9679-9 |

Notes: | We would like to thank Jean-Daniel Boissonnat, Ramsay Dyer, and Arijit Ghosh for pointing out and discussing with us their results on Voronoi diagrams of Riemannian surfaces and manifolds. We are grateful to the anonymous referees for their careful reading of the manuscript, which allowed to correct several problems and to improve the presentation significantly, and for pointing out Kowalick’s thesis [38]. This work was supported by the French ANR Blanc Project ANR-12-BS02-005 (RDAM). Portions of this work were done during a post-doctoral visit of the second author at the Département d’informatique of École normale supérieure, funded by the Fondation Sciences Mathématiques de Paris. Portions of this work were done while the third author was a Ph.D. student at the Département d’informatique of École normale supérieure. |

Open access: | yes (repository) |

IST Austria Authors

Related IST Austria Work