Felix Schröder

1paper

1 Paper

53.3CGMar 16
Holes in Convex and Simple Drawings

Helena Bergold, Joachim Orthaber, Manfred Scheucher et al.

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.