Crossings between non-homotopic edges

Pach, János and Tardos, Gábor and Tóth, Géza (2022) Crossings between non-homotopic edges. JOURNAL OF COMBINATORIAL THEORY SERIES B, 156. pp. 389-404. ISSN 0095-8956

Preview

Text 1-s2.0-S009589562200051X-main.pdf Available under License Creative Commons Attribution. Download (412kB) | Preview

Abstract

A multigraph drawn in the plane is called non-homotopic if no pair of its edges connecting the same pair of vertices can be continuously transformed into each other without passing through a vertex, and no loop can be shrunk to its end-vertex in the same way. Edges are allowed to intersect each other and themselves. It is easy to see that a non-homotopic multigraph on n>1 vertices can have arbitrarily many edges. We prove that the number of crossings between the edges of a non-homotopic multigraph with n vertices and m>4n edges is larger than c[Formula presented] for some constant c>0, and that this bound is tight up to a polylogarithmic factor. We also show that the lower bound is not asymptotically sharp as n is fixed and m tends to infinity.

Actions (login required)

Edit Item