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 Ω(n²) 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.

Creative Commons BY 4.0

Sujoy Bhore, Jie Gao, Hung Le, and Csaba Tóth