Computing the second and third systoles of a combinatorial surface
Matthijs Ebbens, Francis Lazarus · Society for Industrial and Applied Mathematics eBooks · 2025
Given a weighted, undirected graph G cellularly embedded on a topological surface S, we describe algorithms to compute the second shortest and third shortest closed walks of G that are neither homotopically trivial in S nor homotopic to the shortest non-trivial closed walk or to each other. Our algorithms run in O (n2 log n ) time for the second shortest walk and in O (n3) time for the third shortest walk. We also show how to reduce the running time for the second shortest homotopically non-trivial closed walk to O (n log n ) when both the genus and the number of boundaries are fixed.