Non-Homotopic Drawings of Multigraphs

A multigraph drawn in the plane is non-homotopic if no two edges connecting the same pair of vertices can be continuously deformed into each other without passing through a vertex, and is k-crossing if every pair of edges (self-)intersects at most k times. We prove that the number of edges in an n-vertex non-homotopic k-crossing multigraph is at most $6^{13n(k+1)}$ , which is a big improvement over previous upper bounds. We also study this problem in the setting of monotone drawings where every edge is an x-monotone curve. We show that the number of edges, m, in such a drawing is at most $2\left(\begin{array}{c}2n\\ k+1\end{array}\right)$ and the number of crossings is $\Omega (\frac{m^{2+1/k}}{n^{1+1/k}})$ . For fixed k these bounds are both best possible up to a constant multiplicative factor.