1 · The essentials
Imagine a finite network of points joined by links, each with a positive length, in which every point can be reached from every other. The distance between two points is the length of the shortest route connecting them. These manuscripts ask whether those distances can be represented in a different mathematical space without changing their relative sizes too much. The main result says yes for networks that can be drawn in the plane without links crossing: one fixed bound on the change works for all such networks. A companion result gives a similar guarantee for networks with a limited structural complexity called treewidth, with the bound depending only on that complexity. The destination space is called real , and both manuscripts are listed as Lean-formalized.
A picture to help (an imperfect image, not to be taken literally)
As an imperfect image, think of replacing a road map with a table of numerical descriptions of its junctions, then comparing those descriptions instead of tracing routes. The guarantee is that this replacement does not compress some route distances vastly more than others, within the bounds stated for each class of network. The image is imperfect because an representation is not itself a road map.
Why it matters
The source presents these results as resolving the planar and bounded-treewidth cases of the Gupta–Newman–Rabinovich–Sinclair conjecture. They give distance-representation guarantees that are independent of the number of vertices and the particular positive edge lengths, subject to the stated graph restrictions. The repository summary also reports uniformly bounded corresponding multicommodity flow–cut gaps.
2 · Going further
Start with a finite connected graph whose edges have arbitrary positive real lengths, and equip its vertices with the shortest-path metric. The question is whether this metric embeds into real with bounded distortion. In this setting, bounded distortion means that, after a common rescaling, all represented distances lie between the original distances and a fixed multiple of them; measures differences by integrating absolute differences.
The main manuscript states that every such planar graph admits an embedding with a universal distortion bound. Thus the bound does not depend on the particular planar graph or its edge lengths. Its abstract describes this as a positive resolution of the planar embedding conjecture, while the repository summary places it within the Gupta–Newman–Rabinovich–Sinclair conjecture.
The companion manuscript treats graphs of bounded treewidth. For each fixed treewidth bound, it states a uniform distortion guarantee for the same kind of shortest-path metric, with distortion depending only on that treewidth bound. These are related guarantees for two specified graph classes, rather than a stated guarantee for all finite connected graphs.
Both manuscripts are marked Lean-formalized. The supplied abstracts state the conclusions but do not describe the construction of the embeddings or the main steps of the arguments, so an argument-level explanation is not available from this source. The flow–cut consequence appears in the repository summary, but its derivation and formalization scope are not specified.
Useful notions
- Graphs, vertices, and edges
- Shortest-path distances with positive edge lengths
- Planar graphs
- Distance distortion and rescaling
- Real L1 spaces
- Treewidth as a graph complexity measure
What was known before / what is new
Before
The source identifies the planar embedding question as a conjecture and the bounded-treewidth question as a case of the Gupta–Newman–Rabinovich–Sinclair conjecture. It supplies no earlier quantitative bounds, partial results, or history of the arguments.
New
The main manuscript establishes a universal distortion bound for real embeddings of finite connected planar graph metrics with arbitrary positive real edge lengths. The companion establishes a bound depending only on treewidth for graphs with a fixed treewidth bound. Both are listed as Lean-formalized, and the repository summary reports bounded corresponding multicommodity flow–cut gaps.
Limits and assumptions
The hypotheses require finite connected graphs and strictly positive real edge lengths. The universal bound applies to planar graphs; the bounded-treewidth result allows the bound to depend on the chosen treewidth bound. No numerical distortion constants or embedding constructions are supplied. Both embedding manuscripts are marked Lean-formalized, but the source does not detail the formalization scope or separately confirm formal verification of the flow–cut consequence. It resolves the two named cases and does not specify the status of other cases of the conjecture.
Mini glossary
- Shortest-path metric —
- The distance between two vertices obtained by taking the smallest total edge length among routes connecting them.
- Planar graph —
- A graph that can be drawn in the plane with edges meeting only at their shared endpoints.
- Real L1 —
- A space of real-valued integrable functions in which distance is measured by the integral of the absolute difference.
- Bounded distortion —
- A guarantee that, after one common rescaling, represented distances stay between the original distances and a fixed multiple of them.
- Treewidth —
- A measure of graph structure expressing how closely a graph can be organized into a tree-like arrangement of vertex groups.
- Lean formalization —
- An expression of mathematical statements and their proofs in Lean for machine checking.
Keywords : Graph metrics · L1 embeddings · Bounded distortion
AI-generated explanation based on the manuscript. Unofficial. Refer to the manuscript for the authoritative version.
3 · Technical details and sources
Claim made in the manuscript (source text)
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.
Verified by Lean: the Lean software checked the part of the reasoning described below, sometimes only part of the manuscript. This does not mean independent mathematicians have validated the result.
Manuscripts in this family
Planar Graph Metrics Embed into L1 with Constant Distortion
23/09/2026We prove that every finite connected planar graph with arbitrary positive real edge lengths embeds into real L1 with a universal distortion bound. This resolves the planar embedding conjecture positively.
L1 Embeddings of Graphs of Bounded Treewidth
23/09/2026For every fixed treewidth bound, the shortest-path metrics of finite connected graphs with arbitrary positive real edge lengths embed into real L1 with uniformly bounded distortion. This resolves the bounded-treewidth case of the Gupta–Newman–Rabinovich–Sinclair conjecture positively.