29 citations · 89 across the 22 of their papers we have counts for
30 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…
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…
On Plane Subgraphs of Complete Topological Drawings
Alfredo García, Alexander Pilz, Javier Tejel
Topological drawings are representations of graphs in the plane, where vertices are represented by points, and edges by simple curves connecting the points. A drawing is simple if…
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…
Augmenting Geometric Graphs with Matchings
Alexander Pilz, Jonathan Rollin, Lena Schlipf +1
We study noncrossing geometric graphs and their disjoint compatible geometric matchings. Given a cycle (a polygon) P we want to draw a set of pairwise disjoint straight-line edges…
Arrangements of Approaching Pseudo-Lines
Stefan Felsner, Alexander Pilz, Patrick Schnider
We consider arrangements of pseudo-lines in the Euclidean plane where each pseudo-line is represented by a bi-infinite connected -monotone curve , $x \in \m…
Bisecting three classes of lines
Alexander Pilz, Patrick Schnider
We consider the following problem: Let be an arrangement of lines in colored red, green, and blue. Does there exist a vertical plane such that…
Minimal Representations of Order Types by Geometric Graphs
Oswin Aichholzer, Martin Balko, Michael Hoffmann +8
In order to have a compact visualization of the order type of a given point set S, we are interested in geometric graphs on S with few edges that unambiguously display the order ty…
Switches in Eulerian graphs
Ahad N. Zehmakan, Jerri Nummenpalo, Alexander Pilz +1
We show that the graph transformation problem of turning a simple graph into an Eulerian one by a minimum number of single edge switches is NP-hard. Further, we show that any simpl…
A new lower bound on the maximum number of plane graphs using production matrices
Clemens Huemer, Alexander Pilz, Rodrigo I. Silveira
We use the concept of production matrices to show that there exist sets of points in the plane that admit crossing-free geometric graphs. This improves the previou…
From Crossing-Free Graphs on Wheel Sets to Embracing Simplices and Polytopes with Few Vertices
Alexander Pilz, Emo Welzl, Manuel Wettstein
A set of points in general position in the plane is called a wheel set if all points but are extreme. We show that for the purpose of counting crossing…
Extending the centerpoint theorem to multiple points
Alexander Pilz, Patrick Schnider
The centerpoint theorem is a well-known and widely used result in discrete geometry. It states that for any point set of points in , there is a point , not…
Transition Operations over Plane Trees
Torrie L. Nichols, Alexander Pilz, Csaba D. Tóth +1
The operation of transforming one spanning tree into another by replacing an edge has been considered widely, both for general and planar straight-line graphs. For the latter, seve…
A Note on the Flip Distance Problem for Edge-Labeled Triangulations
Alexander Pilz
For both triangulations of point sets and simple polygons, it is known that determining the flip distance between two triangulations is an NP-hard problem. To gain more insight int…
Planar 3-SAT with a Clause/Variable Cycle
Alexander Pilz
In the Planar 3-SAT problem, we are given a 3-SAT formula together with its incidence graph, which is planar, and are asked whether this formula is satisfiable. Since Lichtenstein'…
Geodesic Order Types
Oswin Aichholzer, Matias Korman, Alexander Pilz +1
The geodesic between two points and in the interior of a simple polygon~ is the shortest polygonal path inside that connects to . It is thus the natural gener…
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…
Induced Ramsey-type results and binary predicates for point sets
Martin Balko, Jan Kynčl, Stefan Langerman +1
Let and be positive integers and let be a finite point set in general position in the plane. We say that is -Ramsey if there is a finite point set such t…
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…
An Optimal Algorithm for Reconstructing Point Set Order Types from Radial Orderings
Oswin Aichholzer, Vincent Kusters, Wolfgang Mulzer +2
Let be a set of labeled points in the plane. The radial system of describes, for each , the order in which a ray that rotates around encounters the points i…
Ham-Sandwich Cuts for Abstract Order Types
Stefan Felsner, Alexander Pilz
The linear-time ham-sandwich cut algorithm of Lo, Matoušek, and Steiger for bi-chromatic finite point sets in the plane works by appropriately selecting crossings of the lines in t…
The Dual Diameter of Triangulations
Matias Korman, Stefan Langerman, Wolfgang Mulzer +3
Let $\Poly$ be a simple polygon with vertices. The \emph{dual graph} $\triang^*$ of a triangulation~$\triang$ of~$\Poly$ is the graph whose vertices correspond to the bounded f…
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…