In a preprint dated September 23, 2026, OpenAI (OpenAI 2026) proved the planar embedding conjecture, a long-standing problem connecting the geometry of metric spaces with graph theory and network routing.
Imagine a road network. The distance between two junctions is the length of the shortest route connecting them. Can we assign coordinates to the junctions so that these distances are approximately preserved by a simple formula?
Let be a finite connected undirected graph, with a positive length assigned to every edge. The length of a path is the sum of its edge lengths, and the shortest-path distance is the minimum length of a path connecting and . A graph is called planar if it can be drawn in the plane with edges meeting only at their common endpoints.
Our target geometry is particularly simple. For real vectors and , define The resulting space is denoted by . In two dimensions, this is the familiar Manhattan distance: travelling from to along a rectangular street grid requires a total distance of .
An embedding with distortion at most assigns a vector to every vertex so that, after a common rescaling of all coordinates, every distance lies between the original distance and times the original distance.
The planar embedding conjecture, studied by Gupta, Newman, Rabinovich and Sinclair (Gupta et al. 2004), predicted that one constant should work for every planar graph. The number of vertices could be arbitrarily large, and the edge lengths could vary over an arbitrarily large range.
There was substantial evidence for this prediction. In 1999, Rao (Rao 1999) proved that every planar graph with vertices admits such an embedding with distortion at most , where is a universal constant. Constant bounds were also known for several restricted families of planar graphs. The difficulty was to obtain a bound independent of for the entire planar class.
The new result does exactly this.
Theorem. There is a universal constant such that, for every finite connected planar graph with positive edge lengths, there are a positive integer and a map satisfying
The same constant works for every graph and every assignment of positive edge lengths. The dimension may depend on the graph. The theorem concerns all pairs of vertices simultaneously, including pairs that are very close together and pairs separated by the full diameter of the network.
Why does the sum of absolute coordinate differences play such an important role?
The answer comes from graph cuts. A subset determines a partition into and its complement. Write if and otherwise. Then is precisely when the cut separates and , and is otherwise.
Assign a nonnegative weight to each cut. The formula defines an distance: simply give vertex the vector with coordinates .
Conversely, distances between finitely many points in an space always admit such a representation by weighted cuts. Thus, the embedding theorem says that the distances in every planar graph can be approximated, within one universal factor, by weighted sums of elementary separations into two parts.
The proof constructs these separations at many distance scales. The central difficulty is to make nearby vertices remain close while ensuring that every distant pair is sufficiently separated. Combining constructions at different scales can introduce a loss that grows with the number of scales. The new argument uses planarity to coordinate local modifications and control their interactions, keeping the total loss bounded by a universal constant.
There is also a striking consequence for network routing. We have already encountered the connection between metric embeddings and cuts in this earlier post; see also my post on the sparsest cut problem.
Suppose that every edge of a planar network has a capacity, and various pairs of vertices have specified traffic demands. A necessary condition for routing all the traffic is that, across every cut, the total capacity is at least the total demand between vertices on opposite sides.
For several simultaneous demands, these necessary conditions need not guarantee that all traffic can be routed. However, the new theorem implies that, for planar networks, they suffice up to a universal factor: if every cut satisfies the capacity condition, then at least a fraction of every demand can be routed simultaneously, allowing traffic to be split among several paths. This follows from the equivalence between metric distortion and the multicommodity flow–cut gap established in (Gupta et al. 2004).