Visibility Graphs: Many Conjectures and a Few Theorems

David Wood, Monash University, Melbourne, Australia

The visibility graph of a finite point set P has vertex set P, where two vertices v, w in P are adjacent if the line segment vw contains no other points in P. In other words, the visibility graph is obtained by drawing a line through each pair of points in P, where two points are adjacent if they are consecutive on a such a line. This talk will survey some fascinating conjectures and will present a few theorems on the theme of visibility graphs. Interesting connections are made with other areas of combinatorial geometry, including the orchard problem and the graph crossing number, as well as other more distant areas of combinatorial mathematics, including Ramsey theory (Hales-Jewett Theorem), elliptic curves, and combinatorial number theory (sum-product estimates and Freiman’s Theorem).