Improved Bounds for Shortest Paths in Dense Distance Graphs

Paweł Gawrychowski, Adam Karczmarz

We study the problem of computing shortest paths in so-called dense distance graphs. Every planar graph $G$ on $n$ vertices can be partitioned into a set of $O(n/r)$ edge-disjoint…