TOP
Search the Dagstuhl Website
Looking for information on the websites of the individual seminars? - Then please:
Not found what you are looking for? - Some of our services have separate websites, each with its own search option. Please check the following list:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Seminars
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Publishing
Within this website:
External resources:
dblp
Within this website:
External resources:
  • the dblp Computer Science Bibliography


Please select your role
to obtain appropriate quick-links.
As a LIPIcs/OASIcs author, you will be invited by e-mail to register at the Dagstuhl Submission Server. The server will guide you through the publication workflow. Preliminary information can be found here:
Quick Links

Dagstuhl Seminar 17072

Applications of Topology to the Analysis of 1-Dimensional Objects

( Feb 12 – Feb 17, 2017 )
(Click in the middle of the image to enlarge)
Permalink
Please use the following short url to reference this page: https://www.dagstuhl.de/17072
Organizers
Contact
Publications
Impacts
Schedule
Motivation
Show Motivation

One-dimensional objects embedded in higher-dimensional spaces are one of the most natural phenomena we encounter: ranging from DNA strands to roads to planetary orbits, they occur at all granularities throughout the sciences. One-dimensional objects are studied under different names in different areas of mathematics and computer science (knots, curves, paths, traces, trajectories). In mathematics, 1-dimensional objects are historically well-studied; however, many application areas demand algorithms that deal with 1-dimensional objects, and so this remains a rich topic of study in computer science.

The goal of this Dagstuhl Seminar is to identify connections and seed new research collaborations along the spectrum from knot theory and topology, to computational topology and computational geometry, all the way to graph drawing. The focus will be on 1-dimensional objects embedded in 2- and 3-dimensional spaces, as this is both the most fundamental setting in many applications, as well as the setting where the discrepancy between generic mathematical theory and potential algorithmic solutions is most apparent. This novel combination of areas along a wide spectrum from pure mathematics to computer science has unique potential to provide new fundamental insights for 1-dimensional objects.

Seminar Approach The seminar will consist of a mix of talks and collaborative work on open problems. Longer survey talks will introduce the spectrum of different areas, and shorter talks will give participants the opportunity to present related work. A large portion of the time will be devoted to solving open problems and defining cross-cutting research directions. These will be conducted in several work groups. Topics of study include:

  • Applying computational topology to curve analysis and graph drawing. Applications in this area are in great demand, especially given the rise of massive amounts of data through GIS systems, map analysis, and many other application areas. There are many algorithmically interesting questions that can benefit from the rich mathematical history of related concepts in topology. Homotopy, for example, is notoriously difficult, as even deciding if two curves are homotopic is undecidable in a generic 2-complex; however, many application areas provide restrictions on the inputs that make computation more accessible.
  • Computational and algorithmic knot theory. Practical algorithms are showing their potential through experimentation and computer-assisted proofs, and we are now seeing key breakthroughs in our understanding of the complex relationships between knot theory and complexity theory. Early interactions between mathematicians and computer scientists in these areas have proven extremely fruitful, and as these interactions deepen it is hoped that major unsolved problems in the field will come within reach.
Copyright Benjamin Burton, Maarten Löffler, Carola Wenk, and Erin Moriarty Wolf Chambers
Summary
Show Summary

Description of the seminar

One-dimensional objects embedded in higher-dimensional spaces are one of the most natural phenomena we encounter: ranging from DNA strands to roads to planetary orbits, they occur at all granularities throughout the sciences. Computer-assisted analysis of one-dimensional data is now standard procedure in many sciences; yet the underlying mathematics are not always well understood, preventing the most powerful analytical tools from being used.

Adding to the confusion, one-dimensional objects are studied under different names in different areas of mathematics and computer science (knots, curves, paths, traces, trajectories). In mathematics, 1-dimensional objects are well-understood, and research endeavors have moved on to higher dimensions. On the other hand, many fundamental applications demand solutions that deal with 1-dimensional objects, and these computational problems have largely been studied in separate communities by those unaware of all of the mathematical foundations.

The main goal of the proposed seminar was to identify connections and seed new research collaborations along the spectrum from knot theory and topology, to computational topology and computational geometry, all the way to graph drawing. Each of the invited speakers explored synergies in algorithms concerning 1-dimensional objects embedded in 2- and 3-dimensional spaces, as this is both the most fundamental setting in many applications, as well as the setting where the discrepancy in computational complexity between generic mathematical theory and potential algorithmic solutions is most apparent. In addition, each talk proposed a set of open questions from their research area that could benefit from attention from the other communities, and participants of the seminar were invited to propose their own research questions.

Below, we (the organizers) briefly describe the three main areas bridged; the abstracts of talks in the seminar and preliminary results from the working groups are also outlined later in this report.

Curves in Trajectory Analysis

Applications of computational topology are on the rise; examples include the analysis of GIS data, medical image analysis, graphics and image modeling, and many others. Despite how fundamental the question of topological equivalence is in mathematics, many of the relatively simple settings needed in computational settings (such as the plane or a 2-manifold) have been less examined in mathematics, where computability is known but optimizing algorithms in such "easy" settings has not been of interest until relatively recently.

Homotopy is one of the most fundamental problems to consider in a topological space, as this measure captures continuous deformation between objects. However, homotopy is notoriously difficult, as even deciding if two curves are homotopic is undecidable in a generic 2-complex. Nonetheless, many application settings provide restrictions that make computation more accessible. For example, most GIS applications return trajectories in a planar setting, at which point finding optimal homotopies (for some definition of optimal) becomes tractable.

Homology has been more recently pursued, as finding good homologies reduces to a linear algebra problem which can be solved efficiently. An example of this in the 1-dimensional setting is the recent work by Pokorny on clustering trajectories based on relative persistent homology. However, it is not always clear that optimal homologies provide as intuitive a notion for similarity measures compared with homotopy, and further investigations into applications settings is necessary.

Curves in Knot Theory

A fundamental question in 3-manifold topology is the problem of isotopy. Testing if two curves are ambiently isotopic is a foundational problem of knot theory: essentially, this asks whether two knots in 3-space are topologically equivalent. Problems in knot theory are tightly related to problems in 3-manifold topology, a field that has seen major breakthroughs in recent years, including Perelman's 2002 solution to the geometrisation and Poincaré conjectures, and Agol's recent 2012 proof of the virtual Haken conjecture. Algorithms and computation in these fields are now receiving significant attention from both mathematicians and computer scientists.

Complexity results are surprisingly difficult to come by. For example, one of the most fundamental and best-known problems is detecting whether a curve is knotted. This is known to be in both NP and co-NP; the former result was shown by Hass, Lagarias and Pippenger in 1999, but the latter was proven unconditionally by Lackenby just this year. Finding a polynomial time algorithm remains a major open problem. Hardness results are known for some knot invariants, but (despite being widely expected) no hardness result is known for the general problem of testing two knots for equivalence. Techniques such as randomisation and parameterised complexity are now emerging as fruitful methods for understanding the inherent difficulty of these problems at a deeper level.

Algorithmically, many fundamental problems in knot theory are solved by translating to 3-manifold topology. Here there have been great strides in practical software in recent years: software packages such as SnapPy and Regina are now extremely effective in practice for moderate-sized problems, and have become core tools in the mathematical research process. Nevertheless, their underlying algorithms have significant limitations: SnapPy is based on numerical methods that can lead to numerical instability, and Regina is based on polytope algorithms that can suffer from combinatorial explosions. It is now a major question as to how to design algorithms for knots and 3-manifolds that are exact, implementable, and have provably viable worst-case analyses.

Curves in Graph Drawing

On the computer science end of the spectrum, the study of one-dimensional objects is closely related to Graph Drawing.

Graph Drawing studies the embedding of zero- and one-dimensional features (vertices and edges of graphs) into higher-dimensional spaces; both from an analytic (given an embedding, what can we say about it) and synthetic (come up with a good embedding) point of view. Computational questions (how can we embed a given graph such that it satisfies certain properties / optimises certain criteria) and fundamental questions (which classes of graphs admit which styles of embeddings) have been studied extensively, and a large body of algorithmic results is readily available.

Planarity (non-crossing edges) is a central theme in graph drawing. There is a rich literature discussing which graphs can be drawn planarly, when, and how, as well as how to avoid crossings or other undesirable features in a drawing, such as non-rational vertices. Traditionally, edges have always been embedded as straight line segments; however, there is a recent trend to consider different shapes and curves, drastically increasing the space of possible drawings of a graph. The potential benefits of this broader spectrum are obvious, but the effects (both computational and fundamental) are still ill understood.

Connections between graph drawing and knot theory have long been recognised, yet are still being actively explored. Already in 1983, Conway and Gordon showed that every spatial representation of K_7 contains at least one knotted Hamiltonian cycle. Based on this, in 2013, Politano and Rowland characterised which knots appear as Hamiltonian cycles in canonical book embeddings of complete graphs (as defined by Otsuki in 1996).

Goals and Results of this Seminar

Now is an exciting time for computational and algorithmic knot theory: practical algorithms are showing their potential through experimentation and computer-assisted proofs, and we are now seeing key breakthroughs in our understanding of the complex relationships between knot theory and computability and complexity theory. Early interactions between mathematicians and computer scientists in these areas have proven extremely fruitful, and as these interactions deepen it is hoped that major unsolved problems in the field will come within reach.

Similarly, applications for graph drawing and trajectory analysis are in great demand, especially given the rise of massive amounts of data through GIS systems, map analysis, and many other application areas. However, despite the fact that many problems on curves are seen as mathematically trivial, there are few CS researchers who are truly familiar with the deeper topological results from mathematics. It is likely that many algorithmically interesting questions can benefit from an understanding of this rich history and toolset.

This seminar brought together a group of researchers from computer science and mathematics that study algorithms and mathematical properties of curves in various settings, as the interplay between these two groups is recent. In addition, we invited researchers in applications domains, who often do heuristic analysis of 1-dimensional objects in a variety of settings. Working groups were formed organically, but often allowed participants from various subfields to swap both open problems and favorite tools, and the overview talks discussed favorite tools and techniques from subdomains that may be useful to those in other areas. Concretely, we hope that in addition to the work begun in the working groups, many of these new collaborations will have positive long-term effects on all areas.

Copyright Benjamin Burton, Maarten Löffler, Carola Wenk, and Erin Moriarty Wolf Chambers
Participants
Show Participants
  • Maike Buchin (Ruhr-Universität Bochum, DE) [dblp]
  • Benjamin Burton (The University of Queensland, AU) [dblp]
  • Gregory R. Chambers (University of Chicago, US)
  • Hsien-Chih Chang (University of Illinois - Urbana-Champaign, US) [dblp]
  • Arnaud de Mesmay (University of Grenoble, FR) [dblp]
  • Anne Driemel (TU Eindhoven, NL) [dblp]
  • Parker Evans (Tulane University - New Orleans, US)
  • Brittany Terese Fasy (Montana State University - Bozeman, US) [dblp]
  • Philipp Kindermann (FernUniversität in Hagen, DE) [dblp]
  • Linda Kleist (TU Berlin, DE) [dblp]
  • Boris Klemz (FU Berlin, DE) [dblp]
  • Stephen Kobourov (University of Arizona - Tucson, US) [dblp]
  • Irina Kostitsyna (Free University of Brussels, BE) [dblp]
  • David Letscher (St. Louis University, US) [dblp]
  • Maarten Löffler (Utrecht University, NL) [dblp]
  • Anna Lubiw (University of Waterloo, CA) [dblp]
  • Wouter Meulemans (TU Eindhoven, NL) [dblp]
  • Martin Nöllenburg (TU Wien, AT) [dblp]
  • Tim Ophelders (Eindhoven Univ. of Technology, NL) [dblp]
  • Florian T. Pokorny (KTH Royal Institute of Technology - Stockholm, SE) [dblp]
  • Jessica S. Purcell (Monash University - Clayton, AU) [dblp]
  • Regina Rotman (University of Toronto, CA)
  • Saul Schleimer (University of Warwick - Coventry, GB) [dblp]
  • Lena Schlipf (FernUniversität in Hagen, DE) [dblp]
  • André Schulz (FernUniversität in Hagen, DE) [dblp]
  • Eric Sedgwick (DePaul University - Chicago, US) [dblp]
  • Bettina Speckmann (TU Eindhoven, NL) [dblp]
  • Jonathan Spreer (FU Berlin, DE) [dblp]
  • Frank Staals (Aarhus University, DK) [dblp]
  • Darren Strash (Colgate University - Hamilton, US) [dblp]
  • Dylan Thurston (Indiana University - Bloomington, US) [dblp]
  • Stephan Tillmann (University of Sydney, AU) [dblp]
  • Marc van Kreveld (Utrecht University, NL) [dblp]
  • Mikael Vejdemo-Johansson (CUNY College of Staten Island, US) [dblp]
  • Birgit Vogtenhuber (TU Graz, AT) [dblp]
  • Carola Wenk (Tulane University, US) [dblp]
  • Erin Moriarty Wolf Chambers (St. Louis University, US) [dblp]
Related Seminars
  • Dagstuhl Seminar 19352: Computation in Low-Dimensional Geometry and Topology (2019-08-25 - 2019-08-30) (Details)
  • Dagstuhl Seminar 22062: Computation and Reconfiguration in Low-Dimensional Topological Spaces (2022-02-06 - 2022-02-11) (Details)
  • Dagstuhl Seminar 24072: Triangulations in Geometry and Topology (2024-02-11 - 2024-02-16) (Details)
Classification
  • data structures / algorithms / complexity
Keywords
  • Curves
  • homotopy
  • knot theory
  • graph drawing
Seminar 17072
© 2024 Schloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH
ImprintContactAccessibilityPrivacy