Making Multicurves Cross Minimally on Surfaces

Abstract

On an orientable surface $S$, consider a collection $\Gamma$ of closed curves. The (geometric) intersection number $i_S(\Gamma )$ is the minimum number of self-intersections that a collection ${\Gamma }^{\prime }$ can have, where ${\Gamma }^{\prime }$ results from a continuous deformation (homotopy) of $\Gamma$. We provide algorithms that compute $i_S(\Gamma )$ and such a ${\Gamma }^{\prime }$, assuming that $\Gamma$ is given by a collection of closed walks of length $n$ in a graph $M$ cellularly embedded on $S$, in $O(n\log n)$ time when $M$ and $S$ are fixed. The state of the art is a paper of Despré and Lazarus [SoCG 2017, J. ACM 2019], who compute $i_S(\Gamma )$ in $O(n^2)$ time, and ${\Gamma }^{\prime }$ in $O(n^4)$ time if $\Gamma$ is a single closed curve. Our result is more general since we can put an arbitrary number of closed curves in minimal position. Also, our algorithms are quasi-linear in $n$ instead of quadratic and quartic, and our proofs are simpler and shorter. We use techniques from two-dimensional topology and from the theory of hyperbolic surfaces. Most notably, we prove a new property of the reducing triangulations introduced by Colin de Verdière, Despré, and Dubois [SODA 2024], reducing our problem to the case of surfaces with boundary. As a key subroutine, we rely on an algorithm of Fulek and Tóth [JCO 2020].