Holes in Convex and Simple Drawings
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866918390670557184 |
|---|---|
| author | Bergold, Helena Orthaber, Joachim Scheucher, Manfred Schröder, Felix |
| author_facet | Bergold, Helena Orthaber, Joachim Scheucher, Manfred Schröder, Felix |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_01723 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Holes in Convex and Simple Drawings Bergold, Helena Orthaber, Joachim Scheucher, Manfred Schröder, Felix Computational Geometry Discrete Mathematics Geometric Topology 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. |
| title | Holes in Convex and Simple Drawings |
| topic | Computational Geometry Discrete Mathematics Geometric Topology |
| url | https://arxiv.org/abs/2409.01723 |