On the Computation of Schrijver’s Kernels

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