Holes in Convex and Simple Drawings

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

doi:10.4230/LIPIcs.GD.2024.5

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: Chapter in Book/Report/Conference proceeding › Conference paper › peer-review

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 Erdos-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
Title of host publication	32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)
Editors	Stefan Felsner, Karsten Klein
Place of Publication	Dagstuhl, Germany
Publisher	Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Pages	5:1-5:9
Number of pages	9
Volume	320
ISBN (Electronic)	9783959773430
ISBN (Print)	978-3-95977-343-0
DOIs	https://doi.org/10.4230/LIPIcs.GD.2024.5
Publication status	Published - 28 Oct 2024
Event	32nd International Symposium on Graph Drawing and Network Visualization: GD 2024 - Vienna, Austria Duration: 18 Sept 2024 → 20 Sept 2024 https://graphdrawing.github.io/gd2024/

Publication series

Name	Leibniz International Proceedings in Informatics, LIPIcs
Volume	320
ISSN (Print)	1868-8969

Conference

Conference	32nd International Symposium on Graph Drawing and Network Visualization
Abbreviated title	GD 2024
Country/Territory	Austria
City	Vienna
Period	18/09/24 → 20/09/24
Internet address	https://graphdrawing.github.io/gd2024/

Keywords

convexity hierarchy
Empty Hexagon theorem
empty k-cycle
Erdos-Szekeres theorem
k-gon
k-hole
planar point set
pseudolinear drawing
simple topological graph

ASJC Scopus subject areas

Software

Fields of Expertise

Information, Communication & Computing

Access to Document

10.4230/LIPIcs.GD.2024.5Licence: CC BY 4.0

Cite this

Bergold, H., Orthaber, J., Scheucher, M., & Schröder, F. (2024). Holes in Convex and Simple Drawings. In S. Felsner, & K. Klein (Eds.), 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024) (Vol. 320, pp. 5:1-5:9). Article 5 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 320). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.GD.2024.5

Holes in Convex and Simple Drawings. / Bergold, Helena; Orthaber, Joachim; Scheucher, Manfred et al.
32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). ed. / Stefan Felsner; Karsten Klein. Vol. 320 Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. p. 5:1-5:9 5 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 320).

Research output: Chapter in Book/Report/Conference proceeding › Conference paper › peer-review

Bergold, H, Orthaber, J, Scheucher, M & Schröder, F 2024, Holes in Convex and Simple Drawings. in S Felsner & K Klein (eds), 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). vol. 320, 5, Leibniz International Proceedings in Informatics, LIPIcs, vol. 320, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Dagstuhl, Germany, pp. 5:1-5:9, 32nd International Symposium on Graph Drawing and Network Visualization, Vienna, Austria, 18/09/24. https://doi.org/10.4230/LIPIcs.GD.2024.5

Bergold H, Orthaber J, Scheucher M, Schröder F. Holes in Convex and Simple Drawings. In Felsner S, Klein K, editors, 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Vol. 320. Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. 2024. p. 5:1-5:9. 5. (Leibniz International Proceedings in Informatics, LIPIcs). doi: 10.4230/LIPIcs.GD.2024.5

Bergold, Helena ; Orthaber, Joachim ; Scheucher, Manfred et al. / Holes in Convex and Simple Drawings. 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). editor / Stefan Felsner ; Karsten Klein. Vol. 320 Dagstuhl, Germany : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. pp. 5:1-5:9 (Leibniz International Proceedings in Informatics, LIPIcs).

@inproceedings{dae6925963384fa0b25593e79f288586,

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 Erdos-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.",

keywords = "convexity hierarchy, Empty Hexagon theorem, empty k-cycle, Erdos-Szekeres theorem, k-gon, k-hole, planar point set, pseudolinear drawing, simple topological graph",

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

year = "2024",

month = oct,

day = "28",

doi = "10.4230/LIPIcs.GD.2024.5",

language = "English",

isbn = "978-3-95977-343-0",

volume = "320",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",

pages = "5:1--5:9",

editor = "Stefan Felsner and Karsten Klein",

booktitle = "32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)",

address = "Germany",

note = "32nd International Symposium on Graph Drawing and Network Visualization : GD 2024, GD 2024 ; Conference date: 18-09-2024 Through 20-09-2024",

url = "https://graphdrawing.github.io/gd2024/",

}

TY - GEN

T1 - Holes in Convex and Simple Drawings

AU - Bergold, Helena

AU - Orthaber, Joachim

AU - Scheucher, Manfred

AU - Schröder, Felix

PY - 2024/10/28

Y1 - 2024/10/28

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 Erdos-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 Erdos-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.

KW - convexity hierarchy

KW - Empty Hexagon theorem

KW - empty k-cycle

KW - Erdos-Szekeres theorem

KW - k-gon

KW - k-hole

KW - planar point set

KW - pseudolinear drawing

KW - simple topological graph

UR - https://www.scopus.com/pages/publications/85208800110

U2 - 10.4230/LIPIcs.GD.2024.5

DO - 10.4230/LIPIcs.GD.2024.5

M3 - Conference paper

SN - 978-3-95977-343-0

VL - 320

T3 - Leibniz International Proceedings in Informatics, LIPIcs

SP - 5:1-5:9

BT - 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)

A2 - Felsner, Stefan

A2 - Klein, Karsten

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik

CY - Dagstuhl, Germany

T2 - 32nd International Symposium on Graph Drawing and Network Visualization

Y2 - 18 September 2024 through 20 September 2024

ER -

Holes in Convex and Simple Drawings

Abstract

Publication series

Conference

Keywords

ASJC Scopus subject areas

Fields of Expertise

Access to Document

Other files and links

Doctoral Program: Discrete Mathematics