Crossings between non-homotopic edges
János Pach, Gábor Tardos, Gézá Tóth · Journal of Combinatorial Theory Series B · 2022
A multigraph drawn in the plane is called non-homotopic if no pair of its edges connecting the same pair of vertices can be continuously transformed into each other without passing through a vertex, and no loop can be shrunk to its end-vertex in the same way. Edges are allowed to intersect each other and themselves. It is easy to see that a non-homotopic multigraph on n>1 vertices can have arbitrarily many edges. We prove that the number of crossings between the edges of a non-homotopic multigraph with n vertices and m>4n edges is larger than cm2n for some constant c>0, and that this bound is tight up to a polylogarithmic factor. We also show that the lower bound is not asymptotically sharp as n is fixed and m tends to infinity.