Family 089Convex and metric geometryLeanNot yet digested

Bounded-distortion L $_{1}$ 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 L

_{1}

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.

Manuscripts in this family · 2

Planar Graph Metrics Embed into L1 with Constant Distortion

Sep 23, 2026·paper.pdfLean

We prove that every finite connected planar graph with arbitrary positive real edge lengths embeds into real L

_{1}

with a universal distortion bound. This resolves the planar embedding conjecture positively.

Full abstract

PDF on GitHub LaTeX source

L1 Embeddings of Graphs of Bounded Treewidth

Sep 23, 2026·paper.pdfLean

For every fixed treewidth bound, the shortest-path metrics of finite connected graphs with arbitrary positive real edge lengths embed into real L

_{1}

with uniformly bounded distortion. This resolves the bounded-treewidth case of the Gupta–Newman–Rabinovich–Sinclair conjecture positively.