Crossing number inequalities for curves on surfaces
By: Alfredo Hubard, Hugo Parlier
Potential Business Impact:
Curves on a surface create more crossings as they grow.
We prove that, as $m$ grows, any family of $m$ homotopically distinct closed curves on a surface induces a number of crossings that grows at least like $(m \log m)^2$. We use this to answer two questions of Pach, Tardos and Toth related to crossing numbers of drawings of multigraphs where edges are required to be non-homotopic. Furthermore, we generalize these results, obtaining effective bounds with optimal growth rates on every orientable surface.
Similar Papers
Crossing numbers of dense graphs on surfaces
Combinatorics
Draws pictures of connected dots with fewer messy lines.
Crossing and non-crossing families
Combinatorics
Find many crossing lines or special groups of points.
On the geometric $k$-colored crossing number of $K_n$
Computational Geometry
Makes drawings with fewer same-colored line crossings.