The Zarankiewicz Problem for Polygon Visibility Graphs

Abstract

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 $\hat{I}\text{c◯}(n\hat{I}\pm (n))$ lower bound.

18 pages, 11 figures