2 citations · 4 across the 8 of their papers we have counts for
10 papers
Larger Crossing Families
Joachim Orthaber, Patrick Schnider
We give the first explicit constant for crossing families of linear size by showing that every set of points in general position in the plane contains a crossing family of size…
Separable Drawings: Extendability and Crossing-Free Hamiltonian Cycles
Oswin Aichholzer, Joachim Orthaber, Birgit Vogtenhuber
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 c…
Subgraph-universal planar graphs for trees
Helena Bergold, Vesna Iršič, Robert Lauff +3
We show that there exists an outerplanar graph on vertices for that contains every tree on vertices as a subgraph. This exten…
Holes in Convex and Simple Drawings
Helena Bergold, Joachim Orthaber, Manfred Scheucher +1
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…
On the Uncrossed Number of Graphs
Martin Balko, Petr Hliněný, Tomáš Masařík +3
Visualizing a graph 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 a…
Graph drawing applications in combinatorial theory of maturity models
Špela Kajzer, Alexander Dobler, Janja Jerebic +3
In this paper, we introduce tiled graphs as models of learning and maturing processes. We show how tiled graphs can combine graphs of learning spaces or antimatroids (partial hyper…
Plane Hamiltonian Cycles in Convex Drawings
Helena Bergold, Stefan Felsner, Meghana M. Reddy +2
A conjecture by Rafla from 1988 asserts that every simple drawing of the complete graph admits a plane Hamiltonian cycle. It turned out that already the existence of much sim…
Towards Crossing-Free Hamiltonian Cycles in Simple Drawings of Complete Graphs
Oswin Aichholzer, Joachim Orthaber, Birgit Vogtenhuber
It is a longstanding conjecture that every simple drawing of a complete graph on vertices contains a crossing-free Hamiltonian cycle. We strengthen this conjecture to "t…
Edge Partitions of Complete Geometric Graphs (Part 2)
Oswin Aichholzer, Johannes Obenaus, Joachim Orthaber +5
Recently, the second and third author showed that complete geometric graphs on vertices in general cannot be partitioned into plane spanning trees. Building up on this wor…
Edge Partitions of Complete Geometric Graphs (Part 1)
Johannes Obenaus, Joachim Orthaber
In this paper, we disprove the long-standing conjecture that any complete geometric graph on vertices can be partitioned into plane spanning trees. Our construction is bas…