Geometry and topology · Oct 6, 2026
Bounded-distortion L1 embeddings of planar and bounded-treewidth graphs
Resolves the planar and bounded-treewidth cases of the Gupta–Newman–Rabinovich–Sinclair conjecture. Shortest-path metrics of finite connected graphs with arbitrary positive edge lengths embed into real L1 with universal distortion for planar graphs, and distortion depending only on treewidth for bounded-treewidth graphs. The corresponding multicommodity flow–cut gaps are uniformly bounded.
Contributors
Unreleased OpenAI model
AI systems: Unreleased OpenAI model