Search Results

Documents authored by Orthaber, Joachim

Document
DOI: 10.4230/LIPIcs.GD.2024.5
Holes in Convex and Simple Drawings

Authors: Helena Bergold, Joachim Orthaber, Manfred Scheucher, and Felix Schröder

Published in: LIPIcs, Volume 320, 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)

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ő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.
Cite as

Helena Bergold, Joachim Orthaber, Manfred Scheucher, and Felix Schröder. Holes in Convex and Simple Drawings. In 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 320, pp. 5:1-5:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bergold_et_al:LIPIcs.GD.2024.5,
  author =	{Bergold, Helena and Orthaber, Joachim and Scheucher, Manfred and Schr\"{o}der, Felix},
  title =	{{Holes in Convex and Simple Drawings}},
  booktitle =	{32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)},
  pages =	{5:1--5:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-343-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{320},
  editor =	{Felsner, Stefan and Klein, Karsten},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2024.5},
  URN =		{urn:nbn:de:0030-drops-212895},
  doi =		{10.4230/LIPIcs.GD.2024.5},
  annote =	{Keywords: simple topological graph, convexity hierarchy, k-gon, k-hole, empty k-cycle, Erd\H{o}s-Szekeres theorem, Empty Hexagon theorem, planar point set, pseudolinear drawing}
}
Document
DOI: 10.4230/LIPIcs.GD.2024.18
On the Uncrossed Number of Graphs

Authors: Martin Balko, Petr Hliněný, Tomáš Masařík, Joachim Orthaber, Birgit Vogtenhuber, and Mirko H. Wagner

Published in: LIPIcs, Volume 320, 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)

Abstract
Visualizing a graph G in the plane nicely, for example, without crossings, is unfortunately not always possible. To address this problem, Masařík and Hliněný [GD 2023] recently asked for each edge of G to be drawn without crossings while allowing multiple different drawings of G. More formally, a collection 𝒟 of drawings of G is uncrossed if, for each edge e of G, there is a drawing in 𝒟 such that e is uncrossed. The uncrossed number unc(G) of G is then the minimum number of drawings in some uncrossed collection of G. No exact values of the uncrossed numbers have been determined yet, not even for simple graph classes. In this paper, we provide the exact values for uncrossed numbers of complete and complete bipartite graphs, partly confirming and partly refuting a conjecture posed by Hliněný and Masařík [GD 2023]. We also present a strong general lower bound on unc(G) in terms of the number of vertices and edges of G. Moreover, we prove NP-hardness of the related problem of determining the edge crossing number of a graph G, which is the smallest number of edges of G taken over all drawings of G that participate in a crossing. This problem was posed as open by Schaefer in his book [Crossing Numbers of Graphs 2018].
Cite as

Martin Balko, Petr Hliněný, Tomáš Masařík, Joachim Orthaber, Birgit Vogtenhuber, and Mirko H. Wagner. On the Uncrossed Number of Graphs. In 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 320, pp. 18:1-18:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{balko_et_al:LIPIcs.GD.2024.18,
  author =	{Balko, Martin and Hlin\v{e}n\'{y}, Petr and Masa\v{r}{\'\i}k, Tom\'{a}\v{s} and Orthaber, Joachim and Vogtenhuber, Birgit and Wagner, Mirko H.},
  title =	{{On the Uncrossed Number of Graphs}},
  booktitle =	{32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)},
  pages =	{18:1--18:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-343-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{320},
  editor =	{Felsner, Stefan and Klein, Karsten},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2024.18},
  URN =		{urn:nbn:de:0030-drops-213028},
  doi =		{10.4230/LIPIcs.GD.2024.18},
  annote =	{Keywords: Uncrossed Number, Crossing Number, Planarity, Thickness}
}
Document
DOI: 10.4230/LIPIcs.GD.2024.34
Separable Drawings: Extendability and Crossing-Free Hamiltonian Cycles

Authors: Oswin Aichholzer, Joachim Orthaber, and Birgit Vogtenhuber

Published in: LIPIcs, Volume 320, 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)

Abstract
Generalizing pseudospherical drawings, we introduce a new class of simple drawings, which we call separable drawings. In a separable drawing, every edge can be closed to a simple curve that intersects each other edge at most once. Curves of different edges might interact arbitrarily. Most notably, we show that (1) every separable drawing of any graph on n vertices in the plane can be extended to a simple drawing of the complete graph K_n, (2) every separable drawing of K_n contains a crossing-free Hamiltonian cycle and is plane Hamiltonian connected, and (3) every generalized convex drawing and every 2-page book drawing is separable. Further, the class of separable drawings is a proper superclass of the union of generalized convex and 2-page book drawings. Hence, our results on plane Hamiltonicity extend recent work on generalized convex drawings by Bergold et al. (SoCG 2024).
Cite as

Oswin Aichholzer, Joachim Orthaber, and Birgit Vogtenhuber. Separable Drawings: Extendability and Crossing-Free Hamiltonian Cycles. In 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 320, pp. 34:1-34:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{aichholzer_et_al:LIPIcs.GD.2024.34,
  author =	{Aichholzer, Oswin and Orthaber, Joachim and Vogtenhuber, Birgit},
  title =	{{Separable Drawings: Extendability and Crossing-Free Hamiltonian Cycles}},
  booktitle =	{32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)},
  pages =	{34:1--34:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-343-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{320},
  editor =	{Felsner, Stefan and Klein, Karsten},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2024.34},
  URN =		{urn:nbn:de:0030-drops-213187},
  doi =		{10.4230/LIPIcs.GD.2024.34},
  annote =	{Keywords: Simple drawings, Pseudospherical drawings, Generalized convex drawings, Plane Hamiltonicity, Extendability of drawings, Recognition of drawing classes}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2024.18
Plane Hamiltonian Cycles in Convex Drawings

Authors: Helena Bergold, Stefan Felsner, Meghana M. Reddy, Joachim Orthaber, and Manfred Scheucher

Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)

Abstract
A conjecture by Rafla from 1988 asserts that every simple drawing of the complete graph K_n admits a plane Hamiltonian cycle. It turned out that already the existence of much simpler non-crossing substructures in such drawings is hard to prove. Recent progress was made by Aichholzer et al. and by Suk and Zeng who proved the existence of a plane path of length Ω(log n / log log n) and of a plane matching of size Ω(n^{1/2}) in every simple drawing of K_n. Instead of studying simpler substructures, we prove Rafla’s conjecture for the subclass of convex drawings, the most general class in the convexity hierarchy introduced by Arroyo et al. Moreover, we show that every convex drawing of K_n contains a plane Hamiltonian path between each pair of vertices (Hamiltonian connectivity) and a plane k-cycle for each 3 ≤ k ≤ n (pancyclicity), and present further results on maximal plane subdrawings.
Cite as

Helena Bergold, Stefan Felsner, Meghana M. Reddy, Joachim Orthaber, and Manfred Scheucher. Plane Hamiltonian Cycles in Convex Drawings. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 18:1-18:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bergold_et_al:LIPIcs.SoCG.2024.18,
  author =	{Bergold, Helena and Felsner, Stefan and M. Reddy, Meghana and Orthaber, Joachim and Scheucher, Manfred},
  title =	{{Plane Hamiltonian Cycles in Convex Drawings}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{18:1--18:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-316-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{293},
  editor =	{Mulzer, Wolfgang and Phillips, Jeff M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.18},
  URN =		{urn:nbn:de:0030-drops-199630},
  doi =		{10.4230/LIPIcs.SoCG.2024.18},
  annote =	{Keywords: simple drawing, convexity hierarchy, plane pancyclicity, plane Hamiltonian connectivity, maximal plane subdrawing}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2022.6
Edge Partitions of Complete Geometric Graphs

Authors: Oswin Aichholzer, Johannes Obenaus, Joachim Orthaber, Rosna Paul, Patrick Schnider, Raphael Steiner, Tim Taubner, and Birgit Vogtenhuber

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)

Abstract
In this paper, we disprove the long-standing conjecture that any complete geometric graph on 2n vertices can be partitioned into n plane spanning trees. Our construction is based on so-called bumpy wheel sets. We fully characterize which bumpy wheels can and in particular which cannot be partitioned into plane spanning trees (or even into arbitrary plane subgraphs). Furthermore, we show a sufficient condition for generalized wheels to not admit a partition into plane spanning trees, and give a complete characterization when they admit a partition into plane spanning double stars. Finally, we initiate the study of partitions into beyond planar subgraphs, namely into k-planar and k-quasi-planar subgraphs and obtain first bounds on the number of subgraphs required in this setting.
Cite as

Oswin Aichholzer, Johannes Obenaus, Joachim Orthaber, Rosna Paul, Patrick Schnider, Raphael Steiner, Tim Taubner, and Birgit Vogtenhuber. Edge Partitions of Complete Geometric Graphs. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 6:1-6:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{aichholzer_et_al:LIPIcs.SoCG.2022.6,
  author =	{Aichholzer, Oswin and Obenaus, Johannes and Orthaber, Joachim and Paul, Rosna and Schnider, Patrick and Steiner, Raphael and Taubner, Tim and Vogtenhuber, Birgit},
  title =	{{Edge Partitions of Complete Geometric Graphs}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{6:1--6:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.6},
  URN =		{urn:nbn:de:0030-drops-160141},
  doi =		{10.4230/LIPIcs.SoCG.2022.6},
  annote =	{Keywords: edge partition, complete geometric graph, plane spanning tree, wheel set}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact