29 citations · 89 across the 22 of their papers we have counts for
5 papers · 1 filter
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…