Representing planar and bounded-treewidth distances by cuts

← All digests

Family 089 · Convex and metric geometry
Importance 5/5 · Provisional editorial rating
Sources consulted 2026-10-14

1. The question

A road network gives a distance between locations: the length of the shortest route connecting them. Can those distances be represented approximately as sums of simple yes-or-no separations? Each separation divides the vertices into two groups and charges a pair only when its endpoints fall on opposite sides.

Such a representation is an embedding into $L^1$, or a space with a taxicab-type distance. It is useful because cuts are easier to organize than arbitrary shortest paths, and because the same geometry measures the gap between routing many simultaneous demands and the bottlenecks detected by cuts.

The family contains two manuscripts. M1 claims one universal distortion bound for every finite planar graph with positive edge lengths. M2 claims a bound for every fixed treewidth, independent of graph size and edge-length ratios. Together they address two major cases of the Gupta–Newman–Rabinovich–Sinclair conjecture, usually abbreviated GNRS.

2. Background and essential definitions

For a finite connected undirected graph $G$ with positive edge lengths, let $d_G(u,v)$ be the shortest-path distance. An embedding $F$ into $L^1$ has distortion at most $C$ if, after a common rescaling,

$$d_G(u,v)\leq\|F(u)-F(v)\|_1\leq C\,d_G(u,v)$$

for every pair. No distance shrinks, and none stretches by more than $C$. An $L^1$ distance is the integral of an absolute difference; in finite-dimensional $\ell_1$, it is the sum of absolute coordinate differences.

A cut is a subset $S$ of the vertices, with associated distance

$$\delta_S(u,v)=|\mathbf1_S(u)-\mathbf1_S(v)|.$$

This is one when the cut separates the pair and zero otherwise. Every finite $L^1$ metric is a nonnegative combination of these cut distances:

$$D(u,v)=\sum_{S\subseteq V}w_S\delta_S(u,v),\qquad w_S\geq0.$$

A planar graph can be drawn without crossing edges. Bounded treewidth is a different condition. A tree decomposition arranges small vertex sets, called bags, on a tree: every edge lies in a bag, and the bags containing any fixed vertex form a connected subtree. If bags have at most $k$ vertices, the decomposition has width at most $k-1$. This measures how well the graph can be organized through small separators.

The two classes are not interchangeable. Large planar grids have unbounded treewidth, while bounded-treewidth graphs need not be planar.

3. Development history and previous partial results

Linial, London and Rabinovich’s 1995 paper, and independent work by Aumann and Rabani, connected metric embeddings to approximate multicommodity flow–cut theorems. Gupta, Newman, Rabinovich and Sinclair’s Cuts, trees and ℓ₁-embeddings of graphs formulated the broader minor-closed picture and established important special cases.

For planar metrics, Rao obtained distortion of order $\sqrt{\log n}$ for $n$ vertices by passing through Euclidean space. That intermediate target has a limitation: even some series-parallel metrics require distortion growing like $\sqrt{\log n}$ into Euclidean space. A constant $L^1$ result therefore needs a route that uses the greater flexibility of cut geometry.

Constant distortion was already known for series-parallel graphs, with optimal constant two, and for planar graphs of fixed outerplanarity. Other results preserved only selected terminal distances, such as pairs on one face, or assumed a nonpositive-curvature realization. Those are substantial partial solutions but do not preserve every pair in every planar graph.

For treewidth, the width-two case was known. Bounded pathwidth, where bags lie on a path rather than a branching tree, also admitted uniform bounds. Random embeddings into dominating trees helped in that setting, but cannot give a uniform bound for all bounded-treewidth graphs: some series-parallel metrics already force logarithmic expected distortion into trees.

Chlamtáč, Krauthgamer and Raghavendra’s local-consistency framework supplied compatible local cut distributions and a transport theorem used in M2. Earlier approximation algorithms based on stronger relaxations contain additional consistency information; their performance does not automatically imply a constant distortion bound for the ordinary metric embedding problem.

4. What the new manuscripts claim

M1 states that a finite universal constant $C$ works for every finite connected planar graph and every assignment of strictly positive real edge lengths. The embedding preserves all vertex-pair distances within that factor. The bound is independent of vertex count, diameter and the ratio of largest to smallest positive distances.

M2 states that for each integer $k\geq2$, a finite constant $C_k$ works for every graph admitting bags of cardinality at most $k$. It is independent of the number of bags, their tree’s depth and all edge-length ratios. The target can be finite-dimensional real $\ell_1$. The manuscript establishes existence of $C_k$, without an explicit estimate for its dependence on $k$.

A flow consequence explains the relevance of these constants. Give edges capacities and vertex pairs nonnegative demands. Let $\lambda_*$ be the largest common factor by which all demands can be routed simultaneously, allowing flows to split. Let $\phi_*$ be the smallest ratio of crossing capacity to separated demand over eligible cuts. Necessarily $\lambda_*\leq\phi_*$. The claimed embeddings, through the established flow–cut equivalence, give

$$\lambda_*\leq\phi_*\leq C\lambda_*$$

for planar graphs, and the same statement with $C_k$ for bounded bag size, whenever $\lambda_*>0$.

Using the excluded-planar-minor theorem, M2 also yields a uniform bound for graphs excluding any fixed planar graph as a minor. Combining both manuscripts with a reduction of Lee and Sidiropoulos gives bounds for their fixed-parameter almost-embeddable families. These roughly consist of a bounded-genus part with bounded-width attachments and boundedly many extra vertices. General gluing along larger cliques remains outside the conclusion.

5. Why the advance matters

Importance: 5/5. Constant distortion for all planar graph metrics is a central metric-embedding problem with direct consequences for network routing and cut relaxations. Removing every dependence on graph size and the number of distance scales would be a qualitative improvement over a slowly growing logarithmic bound.

The bounded-treewidth result matters for a different reason: it permits arbitrary branching in the decomposition. A graph can be locally organized by small bags while still having a long, complicated global structure. The claimed constant depends only on bag size, not on how many such pieces must be coordinated.

These results also clarify the right geometric target. A network need not be well represented by one tree, or even by a distribution of dominating trees, to admit a good combination of cuts. Cut metrics allow overlapping separations that do not have to arise from one hierarchical tree geometry.

The score reflects the two major cases and their consequences, while preserving the remaining gap to full GNRS. The manuscripts do not state that every proper minor-closed family has now been handled, nor do they determine the optimal universal planar constant.

6. The main idea

Planar graphs: change cuts without losing the upper bound

M1 realizes a planar graph as vertical columns with switches at selected heights. Height represents distance from a chosen root, and the planar drawing supplies a circular order in which links do not cross. This representation preserves the graph metric.

For each cut label, active points on a column form an upper interval. The measure of labels changing along a vertical segment is controlled by its length, and switches preserve membership. Consequently every path controls the resulting cut distance. This invariant supplies the upper distortion bound even after many updates.

Obtaining lower bounds requires two systems of cuts. The first tries local changes that separate a pair at its natural distance scale. Connected-component refinement can itself certify separation. Pairs that survive both mechanisms have a restricted geometric arrangement near short paths, providing a packing bound specifically for the remaining update sites; the ambient planar metric need not have a uniform packing bound.

The second system uses the circular order to distinguish the two arcs between column indices. A transverse coordinate separates cases where an ordinary distance-like field has equal values on opposite arcs. Local formulas are interpolated so that they agree at their interfaces.

Updates are scheduled at widely separated scales. The probability that coarse changes disrupt a useful chart has a summable bound, and the total movement at later fine scales is too small to erase all separation already gained. Averaging finitely many interleaved schedules covers every pair distance.

Bounded treewidth: preserve local laws and transport separation

M2 assigns a distribution of binary cut labels to each bag. Neighboring distributions agree on their intersection, so they can be glued along the decomposition tree into a global cut law. This consistency gives exact local marginals but does not alone ensure that distant vertices are separated.

The construction uses real-valued functions whose threshold cuts generate these laws. Pairs of functions are updated in opposite directions while preserving their combined cut distribution on the current bag. A quadratic invariant controls their Lipschitz constants after arbitrarily many updates, preventing a cost proportional to tree depth.

Some pairs of functions are temporarily reserved, remaining unchanged along a path of bags. Their common cut measure transports uncertainty from a launch bag to a remote vertex through a bounded-state Markov argument. The number of states depends on bag size, not path length.

One schedule handles pairs sharing a bag; another retains selected anchors across significant distance changes. A compactness argument shows that a pair with arbitrarily poor separation would force a younger protected anchor beyond the youngest one already surviving toward an endpoint, a contradiction. This establishes a positive uniform lower factor, though without an explicit numerical formula for it.

7. Scope, limitations, and open questions

The graphs are finite, connected and undirected, with strictly positive real edge lengths. The routing consequence concerns fractional concurrent flow with arbitrary nonnegative pair demands. It does not assert exact integral routing or equality of every flow and cut optimum.

The constants are uniform within the stated classes. In M2 they may depend on $k$, where $k$ is bag cardinality and the treewidth bound is $k-1$. This indexing distinction avoids shifting the claim by one.

A finite-dimensional target exists, but the statements are not low-dimensional embedding theorems. A cut representation can use many coordinates. For rational edge lengths, M2 combines its existence theorem with earlier algorithms to obtain fixed-parameter approximation consequences; the new existence proof itself does not supply a sharp practical distortion constant.

The full GNRS conjecture additionally requires control under more general clique sums. Gluing pieces at a single vertex is not the same as gluing along larger complete subgraphs. That remaining issue is explicitly retained in the manuscripts.

8. Sources and further reading

M1 gives the planar column construction, its two cut systems and the fixed almost-embeddable consequence. M2 gives consistent bag laws, reserved threshold functions, the compactness argument and the bounded-treewidth statement.

The linked foundational papers explain the flow–cut equivalence and local-consistency framework. Lee and Sidiropoulos’s On the geometry of graphs with a forbidden minor is the primary source for the structural reduction used to combine the two claims.

Source manuscripts

• M1. OpenAI, Planar Graph Metrics Embed into L1 with Constant Distortion (September 23, 2026).
• M2. OpenAI, L1 Embeddings of Graphs of Bounded Treewidth (September 23, 2026).

Sources consulted on 14 October 2026 at repository revision 1581d4c. Download the manuscript citations.