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)}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mn>6</mml:mn> <mml:mrow> <mml:mn>13</mml:mn> <mml:mi>n</mml:mi> <mml:mo>(</mml:mo> <mml:mi>k</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> <mml:mo>)</mml:mo> </mml:mrow> </mml:msup> </mml:math> , 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) $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>2</mml:mn> <mml:mfenced> <mml:mrow> <mml:mtable> <mml:mtr> <mml:mtd> <mml:mrow> <mml:mn>2</mml:mn> <mml:mi>n</mml:mi> </mml:mrow> </mml:mtd> </mml:mtr> <mml:mtr> <mml:mtd> <mml:mrow> <mml:mrow/> <mml:mi>k</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:mtd> </mml:mtr> </mml:mtable> </mml:mrow> </mml:mfenced> </mml:mrow> </mml:math> and the number of crossings is $$\Omega \bigl (\frac{m^{2 + 1/k}}{n^{1 + 1/k}}\bigr )$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>Ω</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> </mml:mrow> <mml:mfrac> <mml:msup> <mml:mi>m</mml:mi> <mml:mrow> <mml:mn>2</mml:mn> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> <mml:mo>/</mml:mo> <mml:mi>k</mml:mi> </mml:mrow> </mml:msup> <mml:msup> <mml:mi>n</mml:mi> <mml:mrow> <mml:mn>1</mml:mn> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> <mml:mo>/</mml:mo> <mml:mi>k</mml:mi> </mml:mrow> </mml:msup> </mml:mfrac> <mml:mrow> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> . For fixed k these bounds are both best possible up to a constant multiplicative factor.