- Dagstuhl Materials Page (Use personal credentials as created in DOOR to log in)
Low-dimensional topological structures are pervasive both in pure mathematics and more applied and natural settings: knots, curves, surfaces and embedded graphs occur as DNA strands, trajectories, meshes, maps and many other examples. This ubiquity leads to very similar objects and questions being studied independently in different communities: from geometric topology, graph algorithms, computational geometry and topology to graph drawing. In all these groups, there is a strong need and interest to develop efficient algorithms that harness the structure of low-dimensional spaces.
The goal of this Dagstuhl Seminar is to bring together researchers from different communities who are working on low-dimensional topological spaces, in order to foster collaborations and synergies. Indeed, while the mathematical study of these objects has a rich and old history, the study of their algorithmic properties is still in its infancy, and new questions and problems keep coming from theoretical computer science or more applied fields, yielding a fresh and renewed perspective on computation in topological spaces.
This seminar is a follow-up to the Dagstuhl Seminars 17072: “Applications of Topology to the Analysis of 1-Dimensional Objects” and 19352: "Computation in Low-Dimensional Geometry and Topology". The first previous seminar focused on the analysis of one-dimensional objects, and the second one widened this to low-dimensional objects and included the evolution of topological objects over time. While these topics are still very current and will not be excluded from the discussions, for the third iteration, we plan to give a new impetus to the seminar by placing a particular emphasis on the topics related to reconfiguration. How can one structure be changed into another? How far apart are two structures? Such questions lie at the heart of various geometric problems like computing the Fréchet distance as a way to quantify curve similarity, or morphing between two versions of a common graph. In many cases, the combinatorics and the geometry of a reconfiguration space also emerged as important objects of study: examples are associahedra and the flip graph of triangulations or the curve complex in geometric topology.
The main emphasis of the seminar will be to develop collaborations by working together on open problems. To foster communication, we will start with a few longer talks given by speakers that span the various areas, with the goal of quickly developing a strong set of open problems for groups of participants to work on.
This seminar was proposed as a followup to the Dagstuhl Seminars 17072: "Applications of Topology to the Analysis of 1-Dimensional Objects" and 19352: "Computation in Low-Dimensional Geometry and Topology". The goal of these seminars was to bring together researchers from different communities who are working on low-dimensional topological spaces (curves, embedded graphs, knots, surfaces, three-manifolds), in order to foster collaborations and synergies. Indeed, while the mathematical study of these objects has a rich and old history, the study of their algorithmic properties is still in its infancy, and new questions and problems keep coming from theoretical computer science and more applied fields, yielding a fresh and renewed perspective on computation in topological spaces.
The success of previous seminars demonstrated that research in low-dimensional topology is very active and fruitful, and also that there was a strong demand for a new seminar gathering researchers from the various involved communities, namely geometric topology and knot theory, computational geometry and topology, all the way to graph drawing and trajectory analysis.
For this iteration we placed a particular emphasis on topics related to geometric and topological reconfiguration: How can one structure be changed into another? How far apart are two structures? Such questions lie at the heart of various geometric problems such as computing the Fréchet distance as a way to quantify curve similarity, or morphing between two versions of a common graph. In many cases, the combinatorics and the geometry of a reconfiguration space also emerged as important objects of study: examples include associahedra, the flip graphs of triangulations, and the curve complexes in geometric topology.
The seminar started with four overview talks given by researchers in geometric topology, computational geometry, topological dynamics, and graph drawing to motivate and propose open problems that would fit the diverse backgrounds of participants and the specific focus on reconfiguration chosen for this year's workshop. This was followed by an open problem session where we gathered fifteen open problems, some of which were circulated in advance of the meeting. The remainder of the week was spent actively working on solving these problems in small groups.
The Covid pandemic prevented many participants from attending the seminar physically, and the entirety of the seminar took place in a hybrid setting, with most working groups featuring both online and physical participants. In order to coordinate the progress, we used Coauthor, a tool designed for by Erik Demaine (MIT), which greatly facilitated the collaborations, and also allowed participants to have a record of the work when the seminar concluded. We also held two daily progress report meetings, allowing people to share progress and allow people to switch groups. In addition to the traditional hike, a virtual social meeting was held on Gather.town to foster interactions between the online and the physical participants.
We now briefly describe the problems that have been worked on, with a more in-depth survey of the problems and the progress being done being featured farther down in this Dagstuhl Report. Some more open problems that have been proposed but not worked on are also listed at the end of the document.
Two groups worked on questions pertaining to reconfiguring curves in the plane and on surfaces. The group 4.1 investigated problems inspired by nonograms, where one aims at introducing switches at intersections of curves in the plane to remove so-called popular faces. The group 4.5 looked at the reconfiguration graph obtained under the action of local moves on minimal closed (multi-)curves on surfaces, and whether such multi-curves could be realized as the set of geodesics of some hyperbolic metric on the surface.
A different flavor of surfaces was studied by the group 4.4, who investigated how square-tiled surfaces could be transformed under the action of shears of cylinder blocks.
The working group 4.2 studied the longstanding problem of the computational complexity of evaluation the rotation distance between elimination trees in graphs. A different flip graph, namely the one of order-k Delaunay triangulations was the topic of study of group 4.7.
Finally, two groups worked on motion of discrete objects in different contexts. The group 4.3 initiated a generalization of the classical theory of morphings of planar graph when one allows the morph to go through a third dimension. The group 4.6 investigated Turning machines, which is a simple model of molecular robot aiming to fold into specific shapes.
All in all, the seminar fostered a highly collaborative research environment by allowing researchers from very diverse backgrounds to work together on precise problems. While the hybrid setting proved to be a significant challenge, the quality of the equipment at Dagstuhl and the online tools that were used provided a practical way for all the participants to interact and to make progress on problems related to reconfiguration in geometric and topological settings.
- Florestan Brunck (IST Austria - Klosterneuburg, AT)
- Kevin Buchin (TU Eindhoven, NL) [dblp]
- Maike Buchin (Ruhr-Universität Bochum, DE) [dblp]
- Benjamin Burton (The University of Queensland - Brisbane, AU) [dblp]
- Jean Cardinal (UL - Brussels, BE)
- Éric Colin de Verdière (CNRS & LIGM - Marne-la-Vallée) [dblp]
- Arnaud de Mesmay (University Paris-Est - Marne-la-Vallée, FR) [dblp]
- Linda Kleist (TU Braunschweig, DE) [dblp]
- Boris Klemz (Universität Würzburg, DE) [dblp]
- Irina Kostitsyna (TU Eindhoven, NL) [dblp]
- Francis Lazarus (CNRS - Grenoble, FR) [dblp]
- Maarten Löffler (Utrecht University, NL) [dblp]
- Alexander Neuhaus (Ruhr-Universität Bochum, DE)
- Tim Ophelders (Utrecht University, NL) [dblp]
- Alexander Wolff (Universität Würzburg, DE) [dblp]
- Mark Bell (Hampshire, GB)
- Hsien-Chih Chang (Dartmouth College - Hanover, US) [dblp]
- Vincent Delecroix (University of Bordeaux, FR)
- Anne Driemel (Universität Bonn, DE) [dblp]
- Nathan Dunfield (University of Illinois - Urbana Champaign, US) [dblp]
- William Evans (University of British Columbia - Vancouver, CA) [dblp]
- Brittany Terese Fasy (Montana State University - Bozeman, US) [dblp]
- Fabrizio Frati (University of Rome III, IT) [dblp]
- Niloufar Fuladi (University Paris-Est - Marne-la-Vallée, FR)
- Elisa Goujard (University of Bordeaux, FR)
- Luke Jeffreys (University of Bristol, GB)
- Anna Lubiw (University of Waterloo, CA) [dblp]
- Torsten Mütze (University of Warwick - Coventry, GB)
- Hugo Parlier (University of Luxembourg, LU) [dblp]
- Lionel Pournin (Université Paris Nord - Villetaneuse, FR)
- Jessica S. Purcell (Monash University - Clayton, AU) [dblp]
- Saul Schleimer (University of Warwick - Coventry, GB) [dblp]
- Lena Schlipf (Universität Tübingen, DE) [dblp]
- Eric Sedgwick (DePaul University - Chicago, US) [dblp]
- Rodrigo I. Silveira (UPC Barcelona Tech, ES) [dblp]
- Jonathan Spreer (University of Sydney, AU) [dblp]
- Stephan Tillmann (University of Sydney, AU) [dblp]
- Uli Wagner (IST Austria - Klosterneuburg, AT) [dblp]
- Carola Wenk (Tulane University - New Orleans, US) [dblp]
- Erin Moriarty Wolf Chambers (St. Louis University, US) [dblp]
- Computational Complexity
- Computational Geometry
- Data Structures and Algorithms
- Geometric Topology