Optimal system of loops on an orientable surface

DOI10.1007/S00454-004-1150-2MaRDI QIDQ1773896zbMATH OpenOpenAlexFDO

Authors Francis Lazarus, Éric Colin de Verdière

Publication date 28 April 2005

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00454-004-1150-2

zbMATH Keywords

algorithm with polynomial running timecombinatorial surfacehomotopy class

Mathematics Subject Classification ID

Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Software, source code, etc. for problems pertaining to manifolds and cell complexes (57-04) General topology of complexes (57Q05)

Review text

Let \(M\) be a compact orientable surface with empty boundary; as it is well-known, a \textit{(fundamental) system of loops} for \(M\) is a collection of simple loops on \(M\) with a common point \(v_{0}\), pairwise disjoint except at \(v_{0}\), which cut \(M\) into a topological disk (for details, see [\textit{J. Stillwell}, Classical topology and combinatorial group theory. Graduate Texts in Mathematics, 72, Springer-Verlag (1980; Zbl 0453.57001)], chapter 1.4). The present paper takes into account the case of an orientable \textit{combinatorial} surface \(M\) whose edges have positive weights, and faces the problem of searching for \textit{optimal} (i.e. \textit{shortest}, with respect to the given weights) systems of loops homotopic to a given one. The authors describe an iterative procedure yielding such an optimal system and prove that it is made of loops which are shortest simple ones in their homotopy classes. Note that, in case of uniform weights, the corresponding algorithm turns out to have polynomial running time; it might be interesting to compare this fact with the NP-hardness of computing a shortest polynomial scheme for a combinatorial surface (see \textit{J. Erickson} and \textit{S. Har-Peled}, Discrete Comput. Geom. 31 (1), 37--59 (2004; Zbl 1060.68129)]).

Recommendations

• Graph Drawing
• Tightening nonsimple paths and cycles on surfaces
• Computing the shortest essential cycle
• Greedy optimal homotopy and homology generators
• Splitting (complicated) surfaces is hard

Cited in

(11)

• Traces, lengths, and simplicity for loops on surfaces
• Testing graph isotopy on surfaces
• Greedy optimal homotopy and homology generators
• Robust Polylines Tracing for N-Symmetry Direction Field on Triangulated Surfaces
• A Census of Plane Graphs with Polyline Edges
• Computing a canonical polygonal schema of an orientable triangulated surface
• Graph Drawing
• What smooth surfaces can be constructed from total degree 2 splines?
• Schnyder woods for higher genus triangulated surfaces, with applications to encoding
• Splitting (complicated) surfaces is hard
• Localized homology

This page was built for publication: Optimal system of loops on an orientable surface

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1773896)