Dagstuhl Seminar 25212
Metric Sketching and Dynamic Algorithms for Geometric and Topological Graphs
( May 18 – May 23, 2025 )
(Click in the middle of the image to enlarge)
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/25212
Organizers
- Sujoy Bhore (Indian Institute of Technology Bombay - Mumbai, IN)
- Jie Gao (Rutgers University - Piscataway, US)
- Hung Le (University of Massachusetts Amherst, US)
- Csaba Tóth (California State University - Northridge, US)
Contact
- Michael Gerke (for scientific matters)
- Christina Schwarz (for administrative matters)
Shared Documents
- Dagstuhl Materials Page (Use personal credentials as created in DOOR to log in)
Schedule
Our goal was to bring together world-renowned researchers in Computational Geometry, Graph Theory, Data Structures, and Algorithms and collaboratively advance the research agenda for the study of metric sketching, and dynamic algorithms for geometric and topological graphs. The participants identified and investigated fundamental open problems and research directions. In particular, we worked on specific open problems about metric sketching, geometric intersection graphs, geometry of topological graphs, and their applications to dynamic algorithms.
This Dagstuhl Seminar “Metric Sketching and Dynamic Algorithms for Geometric and Topological Graphs” (25212) brought together researchers from four research domains, and harvested the benefits of the significant interplay between fundamental geometric & topological structures, and modern algorithmic paradigms. The general objectives of the seminar were:
- To advance knowledge on metric sketching and dynamic algorithms for geometric and topological graphs, and investigate fundamental open problems and research directions.
- To stimulate inter-disciplinary collaboration between Computer Science (computational geometry, data structure and algorithms) and Mathematics (combinatorics and topological graph theory).
- To catalog the state of the art, and distill major open problems on metric sketching and dynamic algorithms for geometric and topological graphs.
In addition to identifying fundamental research problems on metric sketching and dynamic algorithms for geometric and topological graphs, we shall studied concrete problems chosen by the participants during the seminar. The specific scientific aims of this seminar were:
- Structural properties: Identify key characteristics of classes of geometric and topological graphs, and leverage those understandings to address fundamental challenges of metric sketching.
- Trade-offs: Provide the best possible trade-offs among fundamental aspects for metric sketching mechanisms, e.g., lightness, sparsity, diameter, degree, and others.
- Efficient Algorithms: Develop efficient and robust algorithms for fundamental problems defined on geometric and topological graphs, in both static and dynamic regimes.
Behind the scientific challenges of this seminar lies the pragmatic need for better understanding the complex network systems, such as, banking, education, transportation, healthcare, among others. The scale of the data in any present day network system is huge. Hence, sparsifcation is a natural mechanism of handing such big networks. Moreover, the data is constantly changing. With a huge amount of data, recoumputation is not an option anymore. Recent progress on dynamic/online algorithms led to the development of the current best tools to address some of these problems. Hence, a deeper understanding of geometric data structures helps improve tradeoffs between resource utilization and solution quality.
Creative Commons BY 4.0
Sujoy Bhore, Jie Gao, Hung Le, and Csaba Tóth
Sketching is a basic technique to handle big data: Compress a big input dataset into a small dataset, called a sketch, that (approximately) preserves the important information in the input dataset. A metric space is often given as a distance matrix with Ω(n2) entries, and metric sketching techniques aim to reduce the space to linear. One goal of this Dagstuhl Seminar is to understand different sketching techniques and metric spaces that admit small sketches. Another common approach to handling big datasets is dynamic algorithms. Typically, large datasets do not arrive in a single batch; instead, they are updated over time in small increments. The objective of dynamic algorithms is to respond to data updates quickly, ideally with an update time that is polylogarithmic in the size of the whole dataset.
In this seminar, we consider sketching and dynamic algorithms in the context of geometric intersection graphs and topological graphs. Geometric intersection graphs have been used to model many real-world massive graphs, such as wireless networks. Topological graphs, including planar graphs, have been used in applications such as geographic information systems and motion planning. While geometric intersection graphs and topological graphs are seemingly different, they have common structural properties that allow the transfer of algorithmic techniques between the two domains, which is the motivation of this seminar: Uncovering deeper connections between metric sketching, dynamic algorithms, geometric intersection graphs, and topological graphs. More concretely, we will study: (1) the construction of sketching structures, such as spanners, tree covers, distance oracles, and emulators with optimal parameters for various metrics and graphs, including geometric and topological graphs; (2) dynamic problems in geometric intersections graphs, including connectivity, spanners, shortest paths; and (3) dynamic maintenance of metric sketching structures in topological graphs.
Sujoy Bhore, Jie Gao, Hung Le, and Csaba Tóth
Please log in to DOOR to see more details.
- Sujoy Bhore (Indian Institute of Technology Bombay - Mumbai, IN) [dblp]
- Édouard Bonnet (ENS - Lyon, FR) [dblp]
- Prosenjit Bose (Carleton University - Ottawa, CA) [dblp]
- Sergio Cabello (University of Ljubljana, SI) [dblp]
- Hsien-Chih Chang (Dartmouth College - Hanover, US) [dblp]
- Jonathan Conroy (Dartmouth College - Hanover, US) [dblp]
- Arnold Filtser (Bar-Ilan University - Ramat Gan, IL) [dblp]
- Omrit Filtser (The Open University of Israel - Ra'anana, IL) [dblp]
- Jie Gao (Rutgers University - Piscataway, US) [dblp]
- Sándor Kisfaludi-Bak (Aalto University, FI) [dblp]
- Linda Kleist (Universität Potsdam, DE) [dblp]
- Hung Le (University of Massachusetts Amherst, US) [dblp]
- Paloma Lima (IT University of Copenhagen, DK) [dblp]
- Lazar Milenkovic (Tel Aviv University, IL) [dblp]
- Wolfgang Mulzer (FU Berlin, DE) [dblp]
- Eunjin Oh (POSTECH - Pohang, KR) [dblp]
- Marcin Pilipczuk (University of Warsaw, PL) [dblp]
- Michal Pilipczuk (University of Warsaw, PL) [dblp]
- Liam Roditty (Bar-Ilan University - Ramat Gan, IL) [dblp]
- Csaba Tóth (California State University - Northridge, US) [dblp]
- Karol Wegrzycki (MPI für Informatik - Saarbrücken, DE) [dblp]
- Nicole Wein (University of Michigan - Ann Arbor, US) [dblp]
- Sampson Wong (University of Copenhagen, DK) [dblp]
- Da Wei Zheng (University of Illinois - Urbana-Champaign, US) [dblp]
Classification
- Computational Geometry
- Data Structures and Algorithms
- Discrete Mathematics
Keywords
- geometric spanners
- geometric intersection graphs
- planar metrics
- metric covering
- computational geometry
