Non-homotopic Loops with a Bounded Number of Pairwise Intersections

Abstract: Let

V_{n}

be a set of

n

points in the plane and let

x o t i n V_{n}

. An

x

-loop is a continuous closed curve not containing any point of

V_{n}

. We say that two

x

-loops are non-homotopic if they cannot be transformed continuously into each other without passing through a point of

V_{n}

. For

n = 2

, we give an upper bound

e^{O l e f t (s q r t k i g h t)}

on the maximum size of a family of pairwise non-homotopic

x

-loops such that every loop has fewer than

k

self-intersections and any two loops have fewer than

k

intersections. The exponent

is asymptotically tight. The previous upper bound bound

2^{(2 k)^{4}}

was proved by Pach, Tardos, and T'oth [Graph Drawing 2020]. We prove the above result by proving the asymptotic upper bound

e^{O l e f t (s q r t k i g h t)}

for a similar problem when

x i n V_{n}

, and by proving a close relation between the two problems.

This page was built for publication: Non-homotopic Loops with a Bounded Number of Pairwise Intersections