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)

Publikation: Beitrag in Buch/Bericht/Konferenzband › Beitrag in einem Konferenzband › Begutachtung

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.

Originalsprache	englisch
Titel	32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)
Redakteure/-innen	Stefan Felsner, Karsten Klein
Erscheinungsort	Dagstuhl, Germany
Herausgeber (Verlag)	Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Seiten	5:1-5:9
Seitenumfang	9
Band	320
ISBN (elektronisch)	9783959773430
ISBN (Print)	978-3-95977-343-0
DOIs	https://doi.org/10.4230/LIPIcs.GD.2024.5
Publikationsstatus	Veröffentlicht - 28 Okt. 2024
Veranstaltung	32nd International Symposium on Graph Drawing and Network Visualization: GD 2024 - Vienna, Österreich Dauer: 18 Sept. 2024 → 20 Sept. 2024 https://graphdrawing.github.io/gd2024/

Publikationsreihe

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

Konferenz

Konferenz	32nd International Symposium on Graph Drawing and Network Visualization
Kurztitel	GD 2024
Land/Gebiet	Österreich
Ort	Vienna
Zeitraum	18/09/24 → 20/09/24
Internetadresse	https://graphdrawing.github.io/gd2024/

ASJC Scopus subject areas

Software

Fields of Expertise

Information, Communication & Computing

Zugriff auf Dokument

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

Andere Dateien und Links

Verknüpfung zur Publikation in Scopus

1 Abgeschlossen

DK: Diskrete Mathematik
Sava-Huss, E. (Kontaktperson), Heuberger, C. (Projektleiter), Burkard, R. (Teilnehmer / Mitarbeiter), Krenn, D. (Teilnehmer / Mitarbeiter), Kang, M. (Teilnehmer / Mitarbeiter), Kerber, M. (Konsortialführer/in bzw. Koordinator/in bei Kooperationen mit externen Organisationen), Berkes, I. (Projektleiter), Greinecker, F. (Teilnehmer / Mitarbeiter), Grabner, P. (Projektleiter), Tichy, R. (Projektleiter), Cuno, J. (Teilnehmer / Mitarbeiter), Bazarova, A. (Teilnehmer / Mitarbeiter), Lehner, F. (Kontaktperson), Barroero, F. (Teilnehmer / Mitarbeiter), Woess, W. (Konsortialführer/in bzw. Koordinator/in bei Kooperationen mit externen Organisationen), Kreso, D. (Teilnehmer / Mitarbeiter), Elsholtz, C. (Teilnehmer / Mitarbeiter), Wallner, J. (Projektleiter), Ebner, O. (Teilnehmer / Mitarbeiter), Lehner, F. (Teilnehmer / Mitarbeiter), Klinz, B. (Projektleiter) & Raseta, M. (Teilnehmer / Mitarbeiter)
1/05/10 → 30/06/24
Projekt: Forschungsprojekt

1 Konferenz oder Fachtagung (Teilnahme an/Organisation von)
1 Vortrag bei Konferenz oder Fachtagung

Holes in Convex and Simple Drawings
Orthaber, J. R. (Redner/in)
19 Sept. 2024
Aktivität: Vortrag oder Präsentation › Vortrag bei Konferenz oder Fachtagung › Science to science
32nd International Symposium on Graph Drawing and Network Visualization
Orthaber, J. R. (Teilnehmer/-in)
18 Sept. 2024 → 20 Sept. 2024
Aktivität: Teilnahme an / Organisation von › Konferenz oder Fachtagung (Teilnahme an/Organisation von)

1 Preprint

Holes in Convex and Simple Drawings
Bergold, H., Orthaber, J., Scheucher, M. & Schröder, F., 3 Sept. 2024, 14 S.
Publikation: Arbeitspapier › Preprint

Dieses zitieren

Bergold, H., Orthaber, J., Scheucher, M., & Schröder, F. (2024). Holes in Convex and Simple Drawings. in S. Felsner, & K. Klein (Hrsg.), 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024) (Band 320, S. 5:1-5:9). Artikel 5 (Leibniz International Proceedings in Informatics, LIPIcs; Band 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). Hrsg. / Stefan Felsner; Karsten Klein. Band 320 Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. S. 5:1-5:9 5 (Leibniz International Proceedings in Informatics, LIPIcs; Band 320).

Publikation: Beitrag in Buch/Bericht/Konferenzband › Beitrag in einem Konferenzband › Begutachtung

Bergold, H, Orthaber, J, Scheucher, M & Schröder, F 2024, Holes in Convex and Simple Drawings. in S Felsner & K Klein (Hrsg.), 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Bd. 320, 5, Leibniz International Proceedings in Informatics, LIPIcs, Bd. 320, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Dagstuhl, Germany, S. 5:1-5:9, 32nd International Symposium on Graph Drawing and Network Visualization, Vienna, Österreich, 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, Hrsg., 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Band 320. Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. 2024. S. 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). Hrsg. / Stefan Felsner ; Karsten Klein. Band 320 Dagstuhl, Germany : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. S. 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

Publikationsreihe

Konferenz

ASJC Scopus subject areas

Fields of Expertise

Zugriff auf Dokument

Andere Dateien und Links

Projekte

DK: Diskrete Mathematik

Aktivitäten