Distance Oracles and Labeling Schemes for Planar Graphs (Paweł Gawrychowski)
Channel: IRIF
Date: 10/06/2021

A fundamental question concerning graphs is that of constructing a data structure, called a distance oracle, that allows us to compute the distance between any pair of nodes. The goal is to avoid preprocessing the answer to every possible query while keeping the query time small. This is quite hard if we insist on receiving the exact answer and don't make any assumptions about the graph. A particularly natural class of inputs in this context are planar graphs. It is only recently that we have discovered that strongly subquadratic distance oracle with polylogarithmic query time exists for such graphs. I will present the most recent developments in this and related areas. In particular, I will talk about the so-called informative labeling schemes for distances in planar graphs, which can be seen as a clean distributed version of distance oracles.