May 2, Wednesday 14:15, Room 303, Jacobs Building

Title: Fully Dynamic Approximate Distance Oracles for Planar Graphs via Forbidden-Set Distance Labels

Lecturer: Shiri Chechik

Lecturer homepage : http://www.wisdom.weizmann.ac.il/~/shiric/

Affiliation : Weizmann Institute

Distance oracle is a data structure that provides fast answers to distance queries. Recently, the problem of designing distance oracles capable of answering restricted distance queries, that is, estimating distances on a subgraph avoiding some forbidden vertices, has attracted a lot of attention. In this talk, we will consider forbidden set distance oracles for planar graphs. I'll present an efficient compact distance oracle that is capable of handing any number of failures. In addition, we will consider a closely related notion of fully dynamic distance oracles. In the dynamic distance oracle problem instead of getting the failures in the query phase, we rather need to handle an adversarial online sequence of update and query operations. Each query operation involves two vertices s and t whose distance needs to be estimated. Each update operation involves inserting/deleting a vertex/edge from the graph. I'll show that our forbidden set distance oracle can be tweaked to give fully dynamic distance oracle with improved bounds compared to the previously known fully dynamic distance oracle for planar graphs. Joint work with Ittai Abraham and Cyril Gavoille