arXiv GD 2021 | tags:[ counting problems non-homotopic loops ]

# Non-homotopic Loops with a Bounded Number of Pairwise Intersections

with Michal Opler, Matas Šileikis, and Pavel ValtrImprovement on our previous work On the Intersections of Non-homotopic Loops.

## Abstract

Let $V = {v_1, \dots, v_n}$ be a set of $n$ points in the plane and let $x \notin V$.
An *$x$-loop* is a continuous closed curve not containing any point of $V$, except for passing exactly once through the point $x$.
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$.
For $n=2$, we give an upper bound $e^{O(\sqrt{k})}$ 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 $O(\sqrt{k})$ is asymptotically tight. The previous upper bound bound $2^{(2k)^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(\sqrt{k})}$ for a similar problem when $x \in V$, and by proving a close relation between the two problems.