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 $Ω(nα(n))$ lower bound.
Fields of Study & Subjects
Computational Geometry and Mesh Generation
3D Modeling in Geospatial Applications
Data Management and Algorithms
Publication details
- Journal / source
- European Journal of Combinatorics
- Volume
- 137
- Pages
- 104420–104420
- Publication date
- 4 July 2026
- Language
- EN