Christian Wulff-Nilsen, University of Copenhagen

Abstract

A distance oracle of a graph is a preferably compact data structure that can efficiently answer queries for the shortest path distance from one query vertex to another. A trivial distance oracle is a look-up table that stores the shortest path distance between any pair of vertices. This oracle has constant query time but requires Theta(n^2) space. For general graphs, this is the best one can hope for for exact shortest path distance queries. In this talk, I will present some recent results I have been involved in which show that for planar graphs, it is possible to get an oracle that reports exact shortest path distances using space truly subquadratic in n (i.e., O(n^{2-epsilon}) for some constant epsilon > 0) and constant or O(log n) query time. The previous best space bounds with polylogarithmic query time in planar graphs were only below Theta(n^2) by log n-factors. I will also briefly mention progress I have obtained for approximate distance oracles in planar graphs

Location: The Theory of Computing Seminar is being held online. Contact the organizers for the link to the seminar. 

See: https://sites.google.com/view/dimacs-theory-seminar/home