Balázs Keszegh

Eyal Ackerman, Balázs Keszegh

Let $\cal C$ be a set of curves in the plane such that no three curves in $\cal C$ intersect at a single point and every pair of curves in $\cal 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 $\cal C$ that touch each other is $O(|{\cal C}|)$. We prove this conjecture for $x$-monotone curves.

Eyal Ackerman, Balázs Keszegh

We prove a quasi-linear upper bound on the size of $K_{t,t}$-free polygon visibility graphs. For visibility graphs of star-shaped and monotone polygons we show a linear bound. In the more general setting of $n$ points on a simple closed curve and visibility pseudo-segments, we provide an $O(n \log n)$ upper bound and an $Ω(nα(n))$ lower bound.