11 papers
Deciding monotonicity of simple drawings of the complete graph
Oswin Aichholzer, Thomas Hackl, Alexander Pilz +2
A drawing of a graph is {\em -monotone} if every vertical line intersects each edge of the graph at most once. We present an time algorithm for deciding whether a simpl…
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…
Central Triangulation under Parallel Flip Operations: The CG:SHOP Challenge 2026
Oswin Aichholzer, Joseph Dorfer, Sándor P. Fekete +3
We give an overview of the 2026 Computational Geometry Challenge targeting the problem of finding a Central Triangulation under Parallel Flip Operations in triangulations of point…
Geometric Give and Take
Oswin Aichholzer, Katharina Klost, Kristin Knorr +2
We consider a special, geometric case of a balancing game introduced by Spencer in 1977. Consider any arrangement of lines in the plane, and assume that each cell…
Garment numbers of bi-colored point sets in the plane
Oswin Aichholzer, Helena Bergold, Simon D. Fink +3
We consider colored variants of a class of geometric-combinatorial questions on -gons and empty -gons that have been started around 1935 by ErdÅs and Szekeres. In our settin…
Structural Properties of Shortest Flip Sequences Between Plane Spanning Trees
Oswin Aichholzer, Joseph Dorfer, Peter Kramer +2
We study the reconfiguration of plane spanning trees on point sets in the plane in convex position, where a reconfiguration step (flip) replaces one edge with another, yielding aga…