Planar Graph Metrics Admit Constant-Distortion Embeddings Into L1

The September 23, 2026 manuscript Planar Graph Metrics Embed into L1 with Constant Distortion claims that every finite, connected, undirected planar graph with positive real edge lengths can be embedded into (L_1) with one universal distortion factor. Each vertex receives a list of real numbers, and the distance between two lists is the sum of their absolute coordinate differences. After rescaling, the embedded distance is at least the graph’s shortest-path distance and at most (C) times that distance. The same (C) works regardless of graph size or edge-length ratios.^†

The proof has to satisfy both sides of that inequality. Too many or too heavy separating cuts would make some pairs too far apart in the embedding. Too few would leave distant vertices insufficiently separated. The upper bound comes from an invariant that limits how much cut distance can accumulate along a path. The more difficult lower bound requires enough labels to separate pairs, even as the construction changes across scales.

This is a claim about graph distances, not a faithful drawing in two dimensions, and it does not assert exact preservation for every planar metric. The square with four unit edges is an exact illustration of how cuts can work: a left-right cut and a bottom-top cut, each of weight one, give distance one to neighboring corners and two to opposite corners. That example shows the mechanism, not the general theorem.

A cut divides vertices into a set and its complement. Give vertices in the set coordinate (w), and all others coordinate zero. A pair differs by (w) exactly when the cut separates it. Combining coordinates from weighted cuts makes the (L_1) distance the sum of the weights of the cuts separating the pair.

The manuscript controls that sum by first reshaping the network into columns without changing its metric. Choose a root and a shortest-path tree; a vertex’s height is its distance from the root. For each non-tree edge, replace it with two branches rising to a common height, then identify their tips at zero cost. If the edge joins (u) and (v), that height is half the sum of the edge length and the two endpoint heights. The triangle inequality makes the branch lengths nonnegative. In the source’s example, endpoint heights two and three and an edge of length three yield branches of lengths two and one, meeting at height four. Zero-length branches are allowed even though original edge lengths are positive.

Now consider one label: the points containing it define one side of a cut. The construction maintains a measured rule that along a vertical segment, the total weight of labels whose membership changes equals the segment’s length. Membership agrees across the zero-cost switches. So along any path, the cut distance between its endpoints is no greater than the path’s vertical length; taking a shortest path gives the upper bound. Because the rule is maintained through updates, it does not add a fresh cost at every scale.

For the lower bound, local charts must produce certificates of separation. Within a chart, points share a scalar field (P) and the same label variables. A label is active when its real coordinate lies below height plus or minus (\kappa P), with the two signs equally weighted. If (a) is the height difference and (b) is (\kappa) times the field difference, the average of the two absolute differences, ((|a+b|+|a-b|)/2), equals the larger of (|a|) and (|b|). Thus the chart can detect field separation without losing height separation. A strict vertical slope bound keeps both thresholds increasing. This is a local identity, not a proof of global separation; it requires shared chart variables.

The role of planarity appears in fitting those local charts together. In a thin height band, the auxiliary column graph is outerplanar. The manuscript’s portal argument says that entrances to a connected outer region cluster near at most two portals; it does not say that there are only two entrances. Three sufficiently separated entrances would create three disjoint connectors between connected high and low regions. Contracting those connectors gives a (K_3) minor, forbidden in an outerplanar graph.

The source omits the quantitative estimates behind this argument. The portals support interpolation using signed distances from single points. Neighboring pieces agree near their interfaces, including in the named formula they use. Fresh random offsets make a small ball unlikely to straddle different formulas.

Two evolving systems of label sets handle the remaining separation problem. System A tries to raise the field near one endpoint while leaving the other alone; if that fails, the existing field supplies a short path with nearly maximal decrease. It also separates active points in different active components, sometimes using an inactive terminal tip as a certificate. Only pairs that survive these tests seed System B. That restriction matters: the bound is on nearby groups of surviving seeds, not on the density of the whole metric space. System B uses fields ordered along the two circular arcs and a signed transverse field to distinguish the sides. These are schematic descriptions of the hard local mechanisms; their detailed proofs are not reproduced.

The final assembly uses three uniform estimates. At scale (r), any one point’s label set moves by at most (mr). An eligible pair at distance between (r) and (2r) receives a certificate of size at least (br) with probability at least (p). Coarser updates are also unlikely to destroy the pair’s common charts. The constants do not depend on the graph.

Run scales far apart—(r), then (r/Q), then (r/Q^2). Later movement at one point totals at most (mr/(Q-1)). An ordinary separation can lose twice that amount; a component certificate involving two endpoints and a tip can lose three times as much. Choosing (Q) large enough preserves at least half the gain. Finitely many interleaved schedules cover all pair distances. Averaging the cut metrics over random outcomes using their probabilities, and then over schedules, gives a uniform lower bound while retaining the upper bound. The manuscript gives the resulting constant as (C=16m/(pb)).

The theorem uses a zero map for a single-vertex graph. The manuscript also states a consequence for the flow-cut gap of undirected planar graphs with nonnegative capacities and nonnegative demands that are not all zero, provided the routable multiplier is positive. This does not prove the full GNRS conjecture for all proper minor-closed families.