Rerouting Curves on Surfaces

Summary · qwen2.5:32b

The study examines the reconfigurability of crossing-free graph embeddings on surfaces by rerouting edges while maintaining vertex positions and avoiding crossings; for matchings, trees, and forests, such reconfiguration is always possible on any orientable surface with genus at least one, including the torus, though it is not universally possible for more general graphs.

Suggested post angle

Exploring the mathematical problem of reconfiguring a graph on a surface as curves, which has applications in real-time rendering and computer graphics.

Excerpt

arXiv:2607.05362v1 Announce Type: cross 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.