2026-08-07T19:43:41Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:21289 2024-10-28T09:51:04Z ddc:004 open_access

Holes in Convex and Simple Drawings Bergold, Helena Orthaber, Joachim Scheucher, Manfred Schröder, Felix simple topological graph convexity hierarchy k-gon k-hole empty k-cycle Erdős-Szekeres theorem Empty Hexagon theorem planar point set pseudolinear drawing 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 study their existence with respect to the convexity hierarchy. 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 will be the structural investigation of pseudolinear subdrawings in convex drawings. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Helena Bergold and Joachim Orthaber and Manfred Scheucher and Felix Schröder 2024 Is Part Of LIPIcs, Volume 320, 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.GD.2024.5 urn:nbn:de:0030-drops-212895 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2024.5 eng https://creativecommons.org/licenses/by/4.0/legalcode