Õptimal Fault-Tolerant Reachability Labeling in Planar Graphs

Abstract

We show how to assign labels of size $\tilde{O}(1)$ to the vertices of a directed planar graph $G$, such that from the labels of any three vertices $s,t,f$ we can deduce in $\tilde{O}(1)$ time whether $t$ is reachable from $s$ in the graph $G\setminus \{f\}$. Previously it was only known how to achieve $\tilde{O}(1)$ queries using a centralized $\tilde{O}(n)$ size oracle [SODA'21].