Seminar Details
Distance Oracles for Planar Graphs
- Start Date: April 21, 2021
- Event Start Time: 11:00 AM
- Event End Time: 12:00 PM
- Seminar Series: Theoretical Computer Science Seminar
- Presenter(s): Christian Wulff-Nilsen - University of Copenhagen
- Event Location: Online Event
- Event Additional Info: <p>Location: The Theory of Computing Seminar is being held online. Contact the organizers for the link to the seminar. </p> <p>See: <a href="https://sites.google.com/view/dimacs-theory-seminar/home">https://sites.google.com/view/dimacs-theory-seminar/home</a></p> <p> </p>
- Presentation Type: Stand Alone Presentation
- 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