In graph theory, a quasi-metric $(T, \delta_T)$ is an Okamura-Seymour quasimetric if there exists an edge-weighted planar embedded directed graph $G = (V, E, w)$ such that $T$ is a set of terminals on the outer face of $G$ and for every pair $(t, t') \in T \times T$, it holds that $\delta_G(t, t') = \delta_T(t, t')$. Recently, Chen and Tan provided a polynomial-time algorithm to test if a given quasi-metric $(T, \delta_T)$ is an Okamura-Seymour quasimetric. A key step in their proof is existential, which supports an efficient testing algorithm but does not imply an efficient embedding algorithm.
Our paper closes this gap by giving an algorithmic implementation of their existential step via linear programming. As a result, we obtain the first polynomial-time algorithm for finding a planar embedding of any given Okamura-Seymour quasimetric $(T, \delta_T)$. As an application, we show how to use our planar embedding of Okamura-Seymour quasimetrics to compute a $(1 + \epsilon)$-approximate single-source shortest path (SSSP) in planar directed graphs in the distributed CONGEST model in $\tilde{O}(D)$ rounds for any fixed $\epsilon \in (0, 1)$, nearly matching a simple lower bound of $\Omega(D)$ and resolving a fundamental problem in this area. The best-known algorithm for this problem has round complexity $\tilde{O}(D^2)$.
Blogger's Review: This paper successfully implements the planar embedding of Okamura-Seymour quasimetrics using linear programming techniques, providing an efficient solution to the single-source shortest path problem in distributed computing. Its polynomial time complexity will likely advance further research in this area and is worth noting.