19 citations · 101 across the 17 of their papers we have counts for
12 papers · 1 filter
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…
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…
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…
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…
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…
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…
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…
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…
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…
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…
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…