On the Intersections of Non-homotopic Loops

0539705 - ÚI 2022 RIV CH eng C - Konferenční příspěvek (zahraniční konf.)
Blažej, V. - Opler, M. - Šileikis, Matas - Valtr, P.
On the Intersections of Non-homotopic Loops.
Algorithms and Discrete Applied Mathematics. Cham: Springer, 2021 - (Mudgal, A.; Subramanian, C.), s. 196-205. Lecture Notes on Computer Science, 12601. ISBN 978-3-030-67898-2. ISSN 0302-9743.
[CALDAM 2021: The International Conference on Algorithms and Discrete Applied Mathematics /7./. Rupnagar (IN), 11.02.2021-13.02.2021]
Grant CEP: GA ČR(CZ) GJ20-27757Y
Institucionální podpora: RVO:67985807
Klíčová slova: Graph drawing * Non-homotopic loops * Curve intersections * Plane
Obor OECD: Pure mathematics
https://link.springer.com/chapter/10.1007%2F978-3-030-67899-9_15

Let V={v1,…,vn} be a set of n points in the plane and let x∈V . An x-loop is a continuous closed curve not containing any point of V, except of 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 2O(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. This result is inspired by a very recent result of Pach, Tardos, and Tóth who proved the upper bounds 216k4 for the slightly different scenario when x∉V .
Trvalý link: http://hdl.handle.net/11104/0317418