Holes in Convex and Simple Drawings
Abstrak
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.
Penulis (4)
Helena Bergold
Joachim Orthaber
Manfred Scheucher
Felix Schröder
Akses Cepat
- Tahun Terbit
- 2024
- Bahasa
- en
- Sumber Database
- arXiv
- Akses
- Open Access ✓