10 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…
Flip Distance of Non-Crossing Spanning Trees: NP-Hardness and Improved Bounds
HÃ¥vard Bakke Bjerkevik, Joseph Dorfer, Linda Kleist +2
We consider the problem of reconfiguring non-crossing spanning trees on point sets. For a set of points in general position in the plane, the flip graph has a vertex…
Central Triangulation under Parallel Flip Operations: The CG:SHOP Challenge 2026
Oswin Aichholzer, Joseph Dorfer, Sándor P. Fekete +3
We give an overview of the 2026 Computational Geometry Challenge targeting the problem of finding a Central Triangulation under Parallel Flip Operations in triangulations of point…
Sliding Cubes in Parallel
Hugo A. Akitaya, Joseph Dorfer, Peter Kramer +3
We study the classic sliding cube model for programmable matter under parallel reconfiguration in three dimensions, providing novel algorithmic and surprising complexity results in…
Structural Properties of Shortest Flip Sequences Between Plane Spanning Trees
Oswin Aichholzer, Joseph Dorfer, Peter Kramer +2
We study the reconfiguration of plane spanning trees on point sets in the plane in convex position, where a reconfiguration step (flip) replaces one edge with another, yielding aga…
Flip Distance Between Triangulations of Convex Polygons is NP-Complete
Joseph Dorfer
The complexity of determining the minimum number of flips that transform one triangulation of a convex polygon into another has been raised as an open problem by Culik and Wood [In…