Non-Homotopic Drawings of Multigraphs

Abstract 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^{13 n (k + 1)}$$ 6 13 n ( 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) $$ 2 2 n k + 1 and the number of crossings is $$\Omega \bigl (\frac{m^{2 + 1/k}}{n^{1 + 1/k}}\bigr )$$ Ω ( m 2 + 1 / k n 1 + 1 / k ) . For fixed k these bounds are both best possible up to a constant multiplicative factor.