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 <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$6^{13 n (k + 1)}$</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mn>6</mn> <mrow> <mn>13</mn> <mi>n</mi> <mo stretchy="false">(</mo> <mi>k</mi> <mo>+</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> </msup> </math></EquationSource> </InlineEquation>, 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 <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$2 \left( {\begin{array}{c}2n\\ k + 1\end{array}}\right) $</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>2</mn> <mfenced close=")" open="("> <mrow> <mtable> <mtr> <mtd> <mrow> <mn>2</mn> <mi>n</mi> </mrow> </mtd> </mtr> <mtr> <mtd> <mrow> <mrow /> <mi>k</mi> <mo>+</mo> <mn>1</mn> </mrow> </mtd> </mtr> </mtable> </mrow> </mfenced> </mrow> </math></EquationSource> </InlineEquation> and the number of crossings is <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$\Omega \bigl (\frac{m^{2 + 1/k}}{n^{1 + 1/k}}\bigr )$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="normal">Ω</mi> <mrow> <mo maxsize="1.2em" minsize="1.2em" stretchy="true">(</mo> </mrow> <mfrac> <msup> <mi>m</mi> <mrow> <mn>2</mn> <mo>+</mo> <mn>1</mn> <mo stretchy="false">/</mo> <mi>k</mi> </mrow> </msup> <msup> <mi>n</mi> <mrow> <mn>1</mn> <mo>+</mo> <mn>1</mn> <mo stretchy="false">/</mo> <mi>k</mi> </mrow> </msup> </mfrac> <mrow> <mo maxsize="1.2em" minsize="1.2em" stretchy="true">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>. For fixed k these bounds are both best possible up to a constant multiplicative factor.

Non-Homotopic Drawings of Multigraphs

期刊论文
出版模式：

开放获取
发表日期：

2026年6月14日

查看全文

António Girão,
Freddie Illingworth,
Alex Scott,
David R. Wood

摘要

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