Holes in Convex and Simple Drawings
This work addresses combinatorial geometry problems related to point sets and graph drawings, with incremental contributions to understanding holes and cycles in these structures.
The paper investigates the existence of empty k-cycles in simple drawings of complete graphs, proving a generalization of Gerken's empty hexagon theorem for convex drawings and showing that every simple drawing of K_n contains empty 4-cycles, with a construction limiting them to Θ(n^2).
Gons and holes in point sets have been extensively studied in the literature. For simple drawings of the complete graph a generalization of the ErdÅs--Szekeres theorem is known and empty triangles have been investigated. We introduce a notion of $k$-holes for simple drawings and survey generalizations thereof, like empty $k$-cycles. We present a family of simple drawings without $4$-holes and prove a generalization of Gerken's empty hexagon theorem for convex drawings. A crucial intermediate step is the structural investigation of pseudolinear subdrawings in convex drawings. With respect to empty $k$-cycles, we show the existence of empty $4$-cycles in every simple drawing of $K_n$ and give a construction that admits only $Î(n^2)$ of them.