Near-Optimal Distance Oracles for Vertex-Labeled Planar Graphs

Jacob Evald, Viktor Fredslund-Hansen, Christian Wulff-Nilsen

Given an undirected $n$-vertex planar graph $G=(V,E,\omega )$ with non-negative edge weight function $\omega :E\to \mathbb{R}$ and given an assigned label to each vertex, a vertex-label…