The Zarankiewicz Problem for Polygon Visibility Graphs

2025/03/12 by Ackerman, Eyal, Keszegh, Balázs · 2 citations
#Combinatorics (math.CO) #Computational Geometry (cs.CG) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.2503.09115

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.

Cited by

• Compact Representation of Semilinear and Terrain-like Graphs
• C₄-free subgraphs of high degree with geometric applications

Related

• Unsolved Problems in Visibility Graphs of Points, Segments and Polygons
• A Characterization of Visibility Graphs for Pseudo-Polygons
• A survey of Zarankiewicz problems in geometry
• Improved upper bounds on Zarankiewicz numbers
• C₄-free subgraphs of high degree with geometric applications