2025/06/11 by Alfredo Hubard, Hubard, Alfredo, Arnaud de Mesmay +3
Computer Science · Mathematics · #Computational Geometry and Mesh Generation #Geometric and Algebraic Topology #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.2506.09974
In this paper, we provide upper and lower bounds on the crossing numbers of dense graphs on surfaces, which match up to constant factors. First, we prove that if G is a dense enough graph with m edges and Σ is a surface of genus g, then any drawing of G on Σ incurs at least Ω((m2)/(g) log 2 g) crossings. The poly-logarithmic factor in this lower bound is new even in the case of complete graphs and disproves a conjecture of Shahrokhi, Székely and Vrt'o from 1996. Then we prove a geometric converse to this lower bound: we provide an explicit family of hyperbolic surfaces such that for any graph G, sampling the vertices uniformly at random on this surface and connecting them with shortest paths yields O((m2)/(g) log 2 g) crossings in expectation.