The Zarankiewicz Problem for Polygon Visibility Graphs

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 t…