Pulse Journal Club Trending Explore Questions Researchers

Download the App

Join discussions, follow papers, and never miss your next session.

© Synapse Social LLC, 2026Privacy Policy

Home Explore Journal Club Trending

⌘+K

Linear Time Single-Source Shortest Path Algorithms in Euclidean Graph Classes | Synapse

May 29, 2026Open Access

Linear Time Single-Source Shortest Path Algorithms in Euclidean Graph Classes

Key Points

The aim is to establish a linear time single-source shortest path algorithm for certain Euclidean graph classes.
Establish criteria for Euclidean graph classes that allow for linear time shortest path algorithms.
Prove that contracted graphs within these classes exhibit sublinear separators.
Identified specific Euclidean graph classes that permit a linear time algorithm, differing from previously established planar graphs.
Demonstrated the existence of sublinear separators in the contracted graphs of these Euclidean classes.

Abstract

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.

Mark Helpful

Bookmark

Relay

View Full Paper

Mark Helpful

Bookmark

Relay

View Full Paper

Cite This Study

Gudmundsson et al. (Thu,) studied this question.

synapsesocial.com/papers/6a192e95fab5b468c4417bc0 https://doi.org/https://doi.org/10.4230/lipics.socg.2026.55