19 citations · 74 across the 43 of their papers we have counts for
55 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…
Bowties and Hourglasses: Intersections of Double-Wedges (or Stabbing and Avoiding Line Segments)
Daniel Bertschinger, Henry Förster, Fabian Klute +3
We study the common intersection of arrangements of double-wedges. We consider arrangements where double-wedges may be either bowties (which do not contain a vertical line) or hour…
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…
Disjoint Compatibility via Graph Classes
Oswin Aichholzer, Julia Obmann, Pavel Paták +3
Two plane drawings of graphs on the same set of points are called disjoint compatible if their union is plane and they do not have an edge in common. Let be a convex point set…
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…
Bichromatic Perfect Matchings with Crossings
Oswin Aichholzer, Stefan Felsner, Rosna Paul +2
We consider bichromatic point sets with red and blue points and study straight-line bichromatic perfect matchings on them. We show that every such point set in convex posit…
Different Types of Isomorphisms of Drawings of Complete Multipartite Graphs
Oswin Aichholzer, Birgit Vogtenhuber, Alexandra Weinberger
Simple drawings are drawings of graphs in which any two edges intersect at most once (either at a common endpoint or a proper crossing), and no edge intersects itself. We analyze s…
Drawings of Complete Multipartite Graphs Up to Triangle Flips
Oswin Aichholzer, Man-Kwun Chiu, Hung P. Hoang +5
For a drawing of a labeled graph, the rotation of a vertex or crossing is the cyclic order of its incident edges, represented by the labels of their other endpoints. The extended r…
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…
Blocking Delaunay Triangulations from the Exterior
Oswin Aichholzer, Thomas Hackl, Maarten Löffler +4
Given two distinct point sets and in the plane, we say that \emph{blocks} if no two points of are adjacent in any Delaunay triangulation of . Aichholze…
No Selection Lemma for Empty Triangles
Ruy Fabila-Monroy, Carlos Hidalgo-Toscano, Daniel Perz +1
Let be a set of points in general position in the plane. The Second Selection Lemma states that for any family of triangles spanned by , there exists a point of…
Shooting Stars in Simple Drawings of
Oswin Aichholzer, Alfredo García, Irene Parada +2
Simple drawings are drawings of graphs in which two edges have at most one common point (either a common endpoint, or a proper crossing). It has been an open question whether every…
Compatible Spanning Trees in Simple Drawings of
Oswin Aichholzer, Kristin Knorr, Wolfgang Mulzer +6
For a simple drawing of the complete graph , two (plane) subdrawings are compatible if their union is plane. Let be the set of all plane spanning trees on…
Empty Triangles in Generalized Twisted Drawings of
Alfredo García, Javier Tejel, Birgit Vogtenhuber +1
Simple drawings are drawings of graphs in the plane or on the sphere such that vertices are distinct points, edges are Jordan arcs connecting their endpoints, and edges intersect a…
Coloring circle arrangements: New -chromatic planar graphs
Man-Kwun Chiu, Stefan Felsner, Manfred Scheucher +3
Felsner, Hurtado, Noy and Streinu (2000) conjectured that arrangement graphs of simple great-circle arrangements have chromatic number at most . Motivated by this conjecture, we…
Twisted Ways to Find Plane Structures in Simple Drawings of Complete Graphs
Oswin Aichholzer, Alfredo García, Javier Tejel +2
Simple drawings are drawings of graphs in which the edges are Jordan arcs and each pair of edges share at most one point (a proper crossing or a common endpoint). We introduce a sp…
Flipping Plane Spanning Paths
Oswin Aichholzer, Kristin Knorr, Wolfgang Mulzer +3
Let be a planar point set in general position, and let be the set of all plane straight-line paths with vertex set . A flip on a path …
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…
On Crossing-Families in Planar Point Sets
Oswin Aichholzer, Jan Kynčl, Manfred Scheucher +2
A -crossing family in a point set in general position is a set of segments spanned by points of such that all segments mutually cross. In this short note we pres…
Adjacency Graphs of Polyhedral Surfaces
Elena Arseneva, Linda Kleist, Boris Klemz +4
We study whether a given graph can be realized as an adjacency graph of the polygonal cells of a polyhedral surface in . We show that every graph is realizable as a p…
On Compatible Matchings
Oswin Aichholzer, Alan Arroyo, Zuzana Masárová +5
A matching is compatible to two or more labeled point sets of size with labels if its straight-line drawing on each of these point sets is crossing-free. We stu…
Crossing-Optimal Extension of Simple Drawings
Robert Ganian, Thekla Hamm, Fabian Klute +2
In extension problems of partial graph drawings one is given an incomplete drawing of an input graph and is asked to complete the drawing while maintaining certain properties.…
Plane Spanning Trees in Edge-Colored Simple Drawings of
Oswin Aichholzer, Michael Hoffmann, Johannes Obenaus +5
Károlyi, Pach, and Tóth proved that every 2-edge-colored straight-line drawing of the complete graph contains a monochromatic plane spanning tree. It is open if this statement gene…
Rainbow polygons for colored point sets in the plane
David Flores-Peñaloza, Mikio Kano, Leonardo Martínez-Sandoval +5
Given a colored point set in the plane, a perfect rainbow polygon is a simple polygon that contains exactly one point of each color, either in its interior or on its boundary. Let…