8 papers
Geometric Embeddability of Complexes is -complete
Mikkel Abrahamsen, Linda Kleist, Tillmann Miltzow
We show that the decision problem of determining whether a given (abstract simplicial) -complex has a geometric embedding in is complete for the Existential Theory…
Minimum Scan Cover and Variants -- Theory and Experiments
Kevin Buchin, Sándor P. Fekete, Alexander Hill +5
We consider a spectrum of geometric optimization problems motivated by contexts such as satellite communication and astrophysics. In the problem Minimum Scan Cover with Angular Cos…
Upward Point Set Embeddings of Paths and Trees
Elena Arseneva, Pilar Cano, Linda Kleist +4
We study upward planar straight-line embeddings (UPSE) of directed trees on given point sets. The given point set has size at least the number of vertices in the tree. For the…
Minimum Scan Cover with Angular Transition Costs
Sándor P. Fekete, Linda Kleist, Dominik Krupke
We provide a comprehensive study of a natural geometric optimization problem motivated by questions in the context of satellite communication and astrophysics. In the problem Minim…
Folding Polyominoes with Holes into a Cube
Oswin Aichholzer, Hugo A. Akitaya, Kenneth C. Cheung +9
When can a polyomino piece of paper be folded into a unit cube? Prior work studied tree-like polyominoes, but polyominoes with holes remain an intriguing open problem. We present s…
On the edge-vertex ratio of maximal thrackles
Oswin Aichholzer, Linda Kleist, Boris Klemz +2
A drawing of a graph in the plane is a thrackle if every pair of edges intersects exactly once, either at a common vertex or at a proper crossing. Conway's conjecture states that a…