Rerouting Curves on Surfaces
2026-07-06 • Computational Geometry
Computational Geometry
AI summaryⓘ
The authors study how to change one way of drawing a graph on a surface into another, without edges crossing, by moving one edge at a time. Previous work showed that for very simple graphs on a flat surface, this isn’t always possible, but it is on a doughnut-shaped surface (torus). The authors extend these results, proving that for matchings, trees, and forests, such smooth changes are always possible on the torus and other surfaces with at least one hole. They also give some conditions for when this can happen on more complicated surfaces, but show that for more complex graphs, it might not be possible.
graph embeddingcrossing-free embeddinggraph reconfigurationmatchingtreeforesttorusorientable surfaceprojective planegenus
Authors
Timo Brand, Stefan Felsner, Henry Förster, Stephen Kobourov, Anna Lubiw, Yoshio Okamoto, János Pach, Csaba D. Tóth, Géza Tóth, Torsten Ueckerdt, Pavel Valtr
Abstract
We study the problem of reconfiguring a crossing-free embedding of a graph on a surface, with edges represented as curves, into another crossing-free embedding of the same graph on the same surface with the same fixed vertex positions. In this process, we reroute one edge at a time while maintaining crossing-free intermediate embeddings. This problem was introduced by Ito et al. [TALG 2025], who showed that even if the graph is a matching of two edges, reconfiguration is not always possible in the plane, but is always possible on the torus. For matchings of two or more edges, they gave a necessary and sufficient condition for reconfigurable embeddings in the plane, but not on the torus. Our main result is that for matchings, trees and forests, reconfiguration is always possible on the torus, and consequently, on any orientable surface of genus at least one. In addition, we provide sufficient conditions for reconfiguration on orientable surfaces of genus at least one and in the projective plane. For more general graphs, we show that reconfiguration is not always possible.