A triangulation of a surface is k-irreducible if every non-contractible curve has length at least k and any edge contraction breaks this property. Equivalently, every edge belongs to a non-contractible curve of length k and there are no shorter non-contractible curves. We prove that a k-irreducible triangulation of an orientable surface of genus g has O(k²g) triangles, which is optimal. This is an improvement over the previous best bound k^O(k) g² of Gao, Richter and Seymour [Journal of Combinatorial Theory, Series B, 1996].

The geometry of a graph \(G\) embedded on a closed oriented surface \(S\) can be probed by counting the intersections of \(G\) with closed curves on \(S\). Of special interest is the map \(c \mapsto \mu_G(c)\) counting the minimum number of intersections between \(G\) and any curve freely homotopic to a given curve \(c\). Schrijver [On the uniqueness of kernels, 1992] calls \(G\) a kernel if for any proper graph minor \(H\) of \(G\) we have \(\mu_H \lt \mu_G\). Hence, \(G\) admits a minor \(H\) which is a kernel and such that \(\mu_G = \mu_H\). We show how to compute such a minor kernel of \(G\) in \(O(n^3 \log n)\) time where \(n\) is the number of edges of \(G\), and \(g \ge 2\) is the genus of \(S\). Our algorithm leverages a tight bound on the size of minimal bigons in a system of closed curves. It also relies on several subroutines of independent interest including the computation of the area enclosed by a curve and a test of simplicity for the lift of a curve in the universal covering of \(S\).

Consider a weighted, undirected graph cellularly embedded on a topological surface. The function assigning to each free homotopy class of closed curves the length of a shortest cycle within this homotopy class is called the marked length spectrum. The (unmarked) length spectrum is obtained by just listing the length values of the marked length spectrum in increasing order. In this paper, we describe algorithms for computing the (un)marked length spectra of graphs embedded on the torus. More specifically, we preprocess a weighted graph of complexity $n$ in time $O(n^2 \log \log n)$ so that, given a cycle with $\ell$ edges representing a free homotopy class, the length of a shortest homotopic cycle can be computed in $O(\ell+\log n)$ time. Moreover, given any positive integer $k$, the first $k$ values of its unmarked length spectrum can be computed in time $O(k \log n)$. Our algorithms are based on a correspondence between weighted graphs on the torus and polyhedral norms. In particular, we give a weight independent bound on the complexity of the unit ball of such norms. As an immediate consequence we can decide if two embedded weighted graphs have the same marked spectrum in polynomial time. We also consider the problem of comparing the unmarked spectra and provide a polynomial time algorithm in the unweighted case and a randomized polynomial time algorithm otherwise.