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…
Higher Hardness Results for the Reconfiguration of Odd Matchings
Joseph Dorfer
We study the reconfiguration of odd matchings of combinatorial graphs. Odd matchings are matchings that cover all but one vertex of a graph. A reconfiguration step, or flip, is an…
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…
Flipping odd matchings in geometric and combinatorial settings
Oswin Aichholzer, Sofia Brenner, Joseph Dorfer +4
We study the problem of reconfiguring odd matchings, that is, matchings that cover all but a single vertex. Our reconfiguration operation is a so-called flip where the unmatched ve…
Constrained Flips in Plane Spanning Trees
Oswin Aichholzer, Joseph Dorfer, Birgit Vogtenhuber
A flip in a plane spanning tree is the operation of removing one edge from and adding another edge such that the resulting structure is again a plane spanning tree. For tre…
A Linear Time Algorithm for Finding Minimum Flip Sequences between Plane Spanning Paths in Convex Point Sets
Oswin Aichholzer, Joseph Dorfer
We provide a linear time algorithm to determine the flip distance between two plane spanning paths on a point set in convex position. At the same time, we show that the happy edge…