Publications (20)
Representing Directed Trees as Straight Skeletons
Oswin Aichholzer, Therese Biedl, Thomas Hackl +4
The straight skeleton of a polygon is the geometric graph obtained by tracing the vertices during a mitered offsetting process. It is known that the straight skeleton of a simple p…
Empty Monochromatic Simplices
Oswin Aichholzer, Ruy Fabila-Monroy, Thomas Hackl +2
Let be a -colored (finite) set of points in , , in general position, that is, no {} points of lie in a common }-dimensional…
gggenomes: effective and versatile visualizations for comparative genomics
Thomas Hackl, Markus Ankenbrand, Bart van Adrichem +2
The effective visualization of genomic data is crucial for exploring and interpreting complex relationships within and across genes and genomes. Despite advances in developing dedi…
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…
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…
Empty triangles in good drawings of the complete graph
Oswin Aichholzer, Thomas Hackl, Alexander Pilz +3
A good drawing of a simple graph is a drawing on the sphere or, equivalently, in the plane in which vertices are drawn as distinct points, edges are drawn as Jordan arcs connecting…
Coloring Hypergraphs Induced by Dynamic Point Sets and Bottomless Rectangles
Andrei Asinowski, Jean Cardinal, Nathann Cohen +9
We consider a coloring problem on dynamic, one-dimensional point sets: points appearing and disappearing on a line at given times. We wish to color them with k colors so that at an…
Linear transformation distance for bichromatic matchings
Oswin Aichholzer, Luis Barba, Thomas Hackl +2
Let be a set of points in general position, where is a set of blue points and a set of red points. A \emph{-matching} is a plane geometric perf…
Maximizing Maximal Angles for Plane Straight-Line Graphs
Oswin Aichholzer, Thomas Hackl, Michael Hoffmann +5
Let be a plane straight-line graph on a finite point set in general position. The incident angles of a vertex of are the angles between any…
Geodesic-Preserving Polygon Simplification
Oswin Aichholzer, Thomas Hackl, Matias Korman +2
Polygons are a paramount data structure in computational geometry. While the complexity of many algorithms on simple polygons or polygons with holes depends on the size of the inpu…
Flips in combinatorial pointed pseudo-triangulations with face degree at most four
Oswin Aichholzer, Thomas Hackl, David Orden +3
In this paper we consider the flip operation for combinatorial pointed pseudo-triangulations where faces have size 3 or 4, so-called combinatorial 4-PPTs. We show that every combin…
MOSGA: Modular Open-Source Genome Annotator
Roman Martin, Thomas Hackl, Georges Hattab +2
The generation of high-quality assemblies, even for large eukaryotic genomes, has become a routine task for many biologists thanks to recent advances in sequencing technologies. Ho…
Modem Illumination of Monotone Polygons
Oswin Aichholzer, Ruy Fabila-Monroy, David Flores-Peñaloza +3
We study a generalization of the classical problem of the illumination of polygons. Instead of modeling a light source we model a wireless device whose radio signal can penetrate a…
Packing Short Plane Spanning Graphs in Complete Geometric Graphs
Oswin Aichholzer, Thomas Hackl, Matias Korman +5
Given a set of points in the plane, we want to establish a connection network between these points that consists of several disjoint layers. Motivated by sensor networks, we want t…
Flip Graphs of Degree-Bounded (Pseudo-)Triangulations
Oswin Aichholzer, Thomas Hackl, David Orden +4
We study flip graphs of triangulations whose maximum vertex degree is bounded by a constant . In particular, we consider triangulations of sets of points in convex position…
Packing Plane Spanning Trees and Paths in Complete Geometric Graphs
Oswin Aichholzer, Thomas Hackl, Matias Korman +5
We consider the following question: How many edge-disjoint plane spanning trees are contained in a complete geometric graph on any set of points in general position…
Embedding Four-directional Paths on Convex Point Sets
Oswin Aichholzer, Thomas Hackl, Sarah Lutteropp +2
A directed path whose edges are assigned labels "up", "down", "right", or "left" is called \emph{four-directional}, and \emph{three-directional} if at most three out of the four la…
A superlinear lower bound on the number of 5-holes
Oswin Aichholzer, Martin Balko, Thomas Hackl +5
Let be a finite set of points in the plane in general position, that is, no three points of are on a common line. We say that a set of five points from is a -hol…
On -Gons and -Holes in Point Sets
Oswin Aichholzer, Ruy Fabila-Monroy, Hernán González-Aguilar +6
We consider a variation of the classical ErdÅs-Szekeres problems on the existence and number of convex -gons and -holes (empty -gons) in a set of points in the plane.…
Monotone Simultaneous Embedding of Directed Paths
Oswin Aichholzer, Thomas Hackl, Sarah Lutteropp +3
We study monotone simultaneous embeddings of upward planar digraphs, which are simultaneous embeddings where the drawing of each digraph is upward planar, and the directions of the…