If you have ever untangled a ball of yarn, then you have solved a geometric reconfiguration problem. You begin with the object in a particular state and attempt to transform it into a desired target state using a collection of well defined, local operations, often called moves, flips, or reconfiguration steps. For example, one may wish to rearrange binary search trees using rotations, which correspond geometrically to diagonal flips in triangulations of a convex polygon. A planar graph drawing may be converted into a different one by moving vertices in a limited way. In knot theory, knots are transformed using the three classical Reidemeister moves. Although these examples come from different areas, they share a common structure: a space of valid configurations of geometric objects connected by elementary local transformations.

This Dagstuhl Seminar addresses reconfiguration problems on geometric objects, with a particular focus on computational geometry and graph drawing, where transformations are performed through discrete operations. To foster a coherent and productive exchange of ideas, we concentrate on three closely interconnected themes: edge flips in geometric graphs, reconfiguration of dynamic graph drawings, and sweep-based transformations of graph drawings and curve arrangements. Although distinct in their formulations, these topics share fundamental structural principles and methodological challenges. Relevant directions to explore include the following:

• Connectivity, diameters, and radii of flip graphs.
• Algorithmic complexity of flip distance computation.
• Properties of shortest flip sequences.
• Approximation and parameterized complexity.
• Conflict graphs for geometric reconfiguration problems.
• Directed variants of homotopy height for directed acyclic graphs.
• Flip distance of planar graph drawings in dynamic settings.

The aim of the Dagstuhl Seminar is to bring together researchers from different areas of geometric reconfiguration, fostering collaboration and creating synergies across the field. It seeks to encourage exchange between communities while providing opportunities for meaningful interaction. The paramount focus is on allowing ample time for participants to work on specific problems in small, flexible research groups. All participants will be able to move between groups and topics, promoting interaction among researchers with diverse backgrounds.

Creative Commons BY 4.0

Therese Biedl, Christian Rieck, Eva Rotenberg, and Birgit Vogtenhuber