Computing the second and third systoles of a combinatorial surface

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(n 2 log n) time for the second shortest walk and in O(n 3 ) 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.

Our algorithms rely on a careful analysis of the configurations of the first three shortest homotopically non-trivial curves in S. As an intermediate step, we also describe how to compute a shortest essential arc between one pair of vertices or between all pairs of vertices of a given boundary component of S in O(n 2 ) time or O(n 3 ) time, respectively.