5 papers
On Reconstructing a Convex Polygon from Partial Information
Alexander Baumann, Therese Biedl, Mahmoud Elashmawi +4
The reconstruction problem asks to construct a (convex) polygon that has a specified set of features, such as an ordered set of edge-lengths or an ordered set of polygon-angles. In…
Realizing Planar Linkages in Polygonal Domains
Thomas Depian, Carolina Haase, Martin Nöllenburg +1
A linkage consists of a graph and an edge-length function . Deciding whether can be realized as a planar straight-line embedding in $\ma…
Block Stacking, Airplane Refueling, and Robust Appointment Scheduling
Simon Gmeiner, Andreas S. Schulz
How can a stack of identical blocks be arranged to extend beyond the edge of a table as far as possible? We consider a generalization of this classic puzzle to blocks that differ i…
On plane cycles in geometric multipartite graphs
Marco Ricci, Jonathan Rollin, André Schulz +1
A geometric graph is a drawing of a graph in the plane where the vertices are drawn as points in general position and the edges as straight-line segments connecting their endpoints…
Reconfiguration of unit squares and disks: PSPACE-hardness in simple settings
Mikkel Abrahamsen, Kevin Buchin, Maike Buchin +5
We study two well-known reconfiguration problems. Given a start and a target configuration of geometric objects in a polygon, we wonder whether we can move the objects from the sta…