Crossings Between Non-homotopic Edges

We call a multigraph non-homotopic if it can be drawn in the plane in such a way that no two 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. 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.