Linear time single-source shortest path algorithms in Euclidean graph classes
This work addresses a computational geometry problem for researchers and practitioners needing efficient shortest path algorithms in Euclidean settings, representing an incremental advance over prior planar graph results.
The paper tackled the problem of extending linear-time single-source shortest path algorithms from planar graphs to Euclidean graph classes, proving that such classes meeting specific criteria admit linear-time algorithms by showing their contracted graphs have sublinear separators.
In the celebrated paper of Henzinger, Klein, Rao and Subramanian (1997), it was shown that planar graphs admit a linear time single-source shortest path algorithm. Their algorithm unfortunately does not extend to Euclidean graph classes. We give criteria and prove that any Euclidean graph class satisfying the criteria admits a linear time single-source shortest path algorithm. As a main ingredient, we show that the contracted graphs of these Euclidean graph classes admit sublinear separators.