Non-homotopic drawings of multigraphs

Journal article

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(2n, k+1) and the number of crossings is Ω(m²⁺¹⁄ᵏ⁄n¹⁺¹⁄ᵏ). For fixed k these bounds are both best possible up to a constant multiplicative factor.

Authors: Girão, A; Illingworth, F; Scott, A; Wood, DR

• Publication status: Accepted
• Peer review status: Peer reviewed
• Publisher: Springer
• Journal: Discrete & Computational Geometry
• Acceptance date: 2026-05-09
• EISSN: 1432-0444
• ISSN: 0179-5376
• Language: English