4 papers
Point Set Embeddability with List Constraints
Thomas Depian, Joseph Dorfer, Boris Klemz +2
Deciding whether a given graph admits a planar straight-line drawing where each vertex is placed on some point from a given finite point set is known as Point Set Embeddability and…
Minimum Monotone Spanning Trees
Emilio Di Giacomo, Walter Didimo, Eleni Katsanou +3
Given a finite set of points in the plane and a finite set of directions, a geometric spanning tree~ of~ is -monotone if every path in is m…
On Compaction and Realizability of Almost Convex Octilinear Representations
Henry Förster, Giacomo Ortali, Lena Schlip
Octilinear graph drawings are a standard paradigm extending the orthogonal graph drawing style by two additional slopes (+1 and -1). We are interested in two constrained drawing pr…
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…