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 → µ 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 µ H < µ G . Hence, G admits a minor H which is a kernel and such that µ G = µ 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 ⩾ 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.

As a consequence of our minor kernel algorithm and a recent result of Dubois [Making multicurves cross minimally on surfaces, 2024], after a preprocessing that takes O(n 3 log n) time and O(n) space, we are able to compute µ G (c) in O(g(n + ℓ) log(n + ℓ)) time given any closed walk c with ℓ edges. The state-of-the-art algorithm by Colin de Verdière and Erickson [Tightening non-simple paths and cycles on surfaces, 2010] would avoid constructing a kernel but would lead to a computation of µ G (c) in O(gnℓ log(nℓ)) time (with a preprocessing that takes O(gn log n) time and O(gn) space). Another consequence of the computation of minor kernels is the ability to decide in polynomial time whether two graph minors H and H ′ of G satisfy µ H = µ H ′ .