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₁ 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. (Lean)

Manuscripts (2)

Planar Graph Metrics Embed into L1 with Constant Distortion

September 23, 2026 · source · Lean formalization available · cite as \cite{OAI:Planar-Graph-Metrics-Embed-into-L1-with-Constant-Distortion-September-23-2026}

We prove that every finite connected planar graph with arbitrary positive real edge lengths embeds into real L₁ with a universal distortion bound. This resolves the planar embedding conjecture positively.

L1 Embeddings of Graphs of Bounded Treewidth

September 23, 2026 · source · Lean formalization available · cite as \cite{OAI:L1-Embeddings-of-Graphs-of-Bounded-Treewidth-September-23-2026}

For every fixed treewidth bound, the shortest-path metrics of finite connected graphs with arbitrary positive real edge lengths embed into real L₁ with uniformly bounded distortion. This resolves the bounded-treewidth case of the Gupta–Newman–Rabinovich–Sinclair conjecture positively.

Result 089 · Convex and metric geometry. Imported from openai/math, a collection of manuscripts produced by an OpenAI model; results are at different stages of verification. Discussion below is by Lemma members.