The Zarankiewicz Problem for Polygon Visibility Graphs
This work addresses a combinatorial geometry problem for researchers in computational geometry and graph theory, offering incremental improvements in bounding graph sizes.
The authors tackled the Zarankiewicz problem for polygon visibility graphs by proving a quasi-linear upper bound on the size of K_{t,t}-free graphs, with linear bounds for star-shaped and monotone polygons, and provided O(n log n) upper and Ω(nα(n)) lower bounds for points on a simple closed curve with visibility pseudo-segments.
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.