Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2510.18597 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914106047463424 |
|---|---|
| author | Delecroix, Vincent Fontaine, Oscar Lazarus, Francis |
| author_facet | Delecroix, Vincent Fontaine, Oscar Lazarus, Francis |
| contents | 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 μ_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\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$.
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 + \ell) \log(n + \ell))$ time given any closed walk $c$ with $\ell$ 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(g n \ell \log(n \ell))$ 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'}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_18597 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the Computation of Schrijver's Kernels Delecroix, Vincent Fontaine, Oscar Lazarus, Francis Computational Geometry 68U05, 05C85, 57K20 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 μ_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\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$. 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 + \ell) \log(n + \ell))$ time given any closed walk $c$ with $\ell$ 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(g n \ell \log(n \ell))$ 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'}$. |
| title | On the Computation of Schrijver's Kernels |
| topic | Computational Geometry 68U05, 05C85, 57K20 |
| url | https://arxiv.org/abs/2510.18597 |