On the number of tangencies among 1-intersecting curves

EUROCOMB’23

Abstract
Let $\mathcal{C}$ be a set of curves in the plane such that no three curves in $\mathcal{C}$ intersect at a single point and every pair of curves in $\mathcal{C}$ intersect at exactly one point which is either a crossing or a touching point. According to a conjecture of János Pach the number of pairs of curves in $\mathcal{C}$ that touch each other is $O(|\mathcal{C}|)$. We prove this conjecture for $x$-monotone curves.

Pages:
4–11
References

Eyal Ackerman. The maximum number of tangencies among convex regions with a triangle-free intersection graph. In Pach [11], pages 19-30.
https://doi.org/10.1007/978-1-4614-0110-0_3

Eyal Ackerman and Balázs Keszegh. On the number of tangencies among 1-intersecting curves. CoRR, abs/2305.13807, 2023.
https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-001

Eyal Ackerman, Balázs Keszegh, and Dömötör Pálvölgyi. On tangencies among planar curves with an application to coloring L-shapes. In Jaroslav Nešetřil, Guillem Perarnau, Juanjo Rué, and Oriol Serra, editors, Extended Abstracts EuroComb 2021, pages 123-128, Cham, 2021. Springer International Publishing.
https://doi.org/10.1007/978-3-030-83823-2_20

Pankaj K Agarwal, Eran Nevo, János Pach, Rom Pinchasi, Micha Sharir, and Shakhar Smorodinsky. Lenses in arrangements of pseudo-circles and their applications. Journal of the ACM (JACM), 51(2):139-186, 2004.
https://doi.org/10.1145/972639.972641

Maya Bechler-Speicher. A crossing lemma for families of jordan curves with a bounded intersection number. CoRR, abs/1911.07287, 2019.

P. Erdős. On sets of distances of n points. The American Mathematical Monthly, 53(5):248-250, 1946.
https://doi.org/10.1080/00029890.1946.11991674

Dániel Gerbner, Abhishek Methuku, Dániel T. Nagy, Dömötör Pálvölgyi, Gábor Tardos, and Máté Vizer. Turán problems for edge-ordered graphs. Journal of Combinatorial Theory, Series B, 160:66-113, 2023.
https://doi.org/10.1016/j.jctb.2022.12.006

Péter Györgyi, Bálint Hujter, and Sándor Kisfaludi-Bak. On the number of touching pairs in a set of planar curves. Computational Geometry, 67:29-37, 2018.
https://doi.org/10.1016/j.comgeo.2017.10.004

Klara Kedem, Ron Livne, János Pach, and Micha Sharir. On the union of jordan regions and collision-free translational motion amidst polygonal obstacles. Discrete & Computational Geometry, 1(1):59-71, Mar 1986.
https://doi.org/10.1007/BF02187683

Balázs Keszegh and Dömötör Pálvölgyi. The number of tangencies between two families of curves, 2021.

P. Koebe. Kontaktprobleme der konformen Abbildung. Ber. Saechs. Akad. Wiss. Leipzig, Math.-Phys. Kl., 88:141-164, 1936.

J. Pach, editor. Thirty Essays on Geometric Graph Theory. Springer New York, 2012.
https://doi.org/10.1007/978-1-4614-0110-0

János Pach. personal communication.

János Pach and Pankaj K. Agarwal. Combinatorial Geometry, chapter 11, pages 177-178. John Wiley and Sons Ltd, 1995.
https://doi.org/10.1002/9781118033203

János Pach, Natan Rubin, and Gábor Tardos. On the Richter-Thomassen conjecture

about pairwise intersecting closed curves. Combinatorics, Probability and Computing, 25(6):941-958, 2016.
https://doi.org/10.1017/S0963548316000043

János Pach, Natan Rubin, and Gábor Tardos. A crossing lemma for Jordan curves. Advances in Mathematics, 331:908-940, 2018.
https://doi.org/10.1016/j.aim.2018.03.015

János Pach and Micha Sharir. On vertical visibility in arrangements of segments and the queue size in the Bentley-Ottmann line sweeping algorithm. SIAM J. Comput., 20(3):460-470, 1991.
https://doi.org/10.1137/0220029

János Pach and Micha Sharir. On the boundary of the union of planar convex sets. Discrete & Computational Geometry, 21(3):321-328, 1999.
https://doi.org/10.1007/PL00009424

János Pach, Andrew Suk, and Miroslav Treml. Tangencies between families of disjoint regions in the plane. Comput. Geom., 45(3):131-138, 2012.
https://doi.org/10.1016/j.comgeo.2011.10.002

R.B. Richter and C. Thomassen. Intersections of curve systems and the crossing number of C5 × C5. Discrete Comput. Geom., 13(2):149-159, 1995.
https://doi.org/10.1007/BF02574034

V. Rödl. Master's thesis, Charles University, 1973.

Gelasio Salazar. On the Richter-Thomassen conjecture about pairwise intersecting closed curves. J. Comb. Theory, Ser. B, 75(1):56-60, 1999.

Jack Snoeyink and John Hershberger. Sweeping arrangements of curves. In Proceedings of the fifth annual symposium on Computational geometry, pages 354-363. ACM, 1989.
https://doi.org/10.1145/73833.73872

Metrics

0

Views

0

PDF views