Holes in Convex and Simple Drawings

Helena Bergold; Joachim Orthaber; Manfred Scheucher; Felix Schröder

doi:10.48550/arXiv.2409.01723

Holes in Convex and Simple Drawings

Helena Bergold
, Joachim Orthaber
, Manfred Scheucher
, Felix Schröder

Institute of Software Engineering and Artificial Intelligence (7160)

Research output: Working paper › Preprint

Abstract

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\H{o}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.

Original language	English
Number of pages	14
DOIs	https://doi.org/10.48550/arXiv.2409.01723
Publication status	Published - 3 Sept 2024

Fields of Expertise

Information, Communication & Computing

Access to Document

10.48550/arXiv.2409.01723

1 Finished

Doctoral Program: Discrete Mathematics
Sava-Huss, E. (Contact person), Heuberger, C. (Project manager), Burkard, R. (Attendee / Assistant), Krenn, D. (Attendee / Assistant), Kang, M. (Attendee / Assistant), Kerber, M. (Consortium manager resp. coordinator with external organisations), Berkes, I. (Project manager), Greinecker, F. (Attendee / Assistant), Grabner, P. (Project manager), Tichy, R. (Project manager), Cuno, J. (Attendee / Assistant), Bazarova, A. (Attendee / Assistant), Lehner, F. (Contact person), Barroero, F. (Attendee / Assistant), Woess, W. (Consortium manager resp. coordinator with external organisations), Kreso, D. (Attendee / Assistant), Elsholtz, C. (Attendee / Assistant), Wallner, J. (Project manager), Ebner, O. (Attendee / Assistant), Lehner, F. (Attendee / Assistant), Klinz, B. (Project manager) & Raseta, M. (Attendee / Assistant)
1/05/10 → 30/06/24
Project: Research project

1 Conference or symposium (Participation in/Organisation of)
1 Talk at conference or symposium

32nd International Symposium on Graph Drawing and Network Visualization
Orthaber, J. R. (Participant)
18 Sept 2024 → 20 Sept 2024
Activity: Participation in or organisation of › Conference or symposium (Participation in/Organisation of)
Holes in Convex and Simple Drawings
Orthaber, J. R. (Speaker)
19 Sept 2024
Activity: Talk or presentation › Talk at conference or symposium › Science to science

1 Conference paper

Holes in Convex and Simple Drawings
Bergold, H., Orthaber, J., Scheucher, M. & Schröder, F., 28 Oct 2024, 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Felsner, S. & Klein, K. (eds.). Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Vol. 320. p. 5:1-5:9 9 p. 5. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 320).
Research output: Chapter in Book/Report/Conference proceeding › Conference paper › peer-review

Open Access

Cite this

@techreport{18d4a1a2fd78463fba2838d2dc517713,

title = "Holes in Convex and Simple Drawings",

abstract = " 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\textbackslash{}H\{o\}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. ",

author = "Helena Bergold and Joachim Orthaber and Manfred Scheucher and Felix Schr{\"o}der",

note = "This article appears in the proceedings of GD2024",

year = "2024",

month = sep,

day = "3",

doi = "10.48550/arXiv.2409.01723",

language = "English",

type = "WorkingPaper",

}

TY - UNPB

T1 - Holes in Convex and Simple Drawings

AU - Bergold, Helena

AU - Orthaber, Joachim

AU - Scheucher, Manfred

AU - Schröder, Felix

N1 - This article appears in the proceedings of GD2024

PY - 2024/9/3

Y1 - 2024/9/3

N2 - 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\H{o}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.

AB - 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\H{o}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.

U2 - 10.48550/arXiv.2409.01723

DO - 10.48550/arXiv.2409.01723

M3 - Preprint

BT - Holes in Convex and Simple Drawings

ER -

Holes in Convex and Simple Drawings

Abstract

Fields of Expertise

Access to Document

Fingerprint

Projects

Doctoral Program: Discrete Mathematics

Activities

32nd International Symposium on Graph Drawing and Network Visualization