Linear time single-source shortest path algorithms in Euclidean graph classes

Joachim Gudmundsson, Yuan Sha, Sampson Wong

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…