Planar Embedding of Okamura-Seymour Quasimetrics in Polynomial Time with an Application to Distributed SSSP
Hung Le, Hector Tierno, Shuang Yang · 2026
Read Planar Embedding of Okamura-Seymour Quasimetrics in Polynomial Time with an Application to Distributed SSSP by Hung Le, Hector Tierno, Shuang Yang (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-31192.txt.
Introduction
Le and two colleagues settle a gap in the theory of Okamura-Seymour quasimetrics, distance-like functions that fit inside a flat directed graph. Earlier work by Chen and Tan tested in polynomial time whether such a quasimetric exists, but one key step only proved existence. Testing is not the same as building the embedding itself.
Le turns that existence step into an algorithm with linear programming. The result is the first polynomial-time method that actually finds a planar embedding for any given Okamura-Seymour quasimetric. As a payoff, they give a near-optimal distributed algorithm for approximate single-source shortest paths in planar directed graphs. It runs in the CONGEST model in a round count close to the diameter lower bound, resolving a standing open question.
Catalog record
| CREATOR | Hung Le, Hector Tierno, Shuang Yang |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 175 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.31192