The planar embedding conjecture: constant-distortion embeddings of planar graph metrics into $L_1$

Every finite planar graph $G$ induces a shortest-path metric $d_G$ on its vertices, and the central open question — the planar embedding conjecture posed by Gupta, Newman, Rabinovich and Sinclair (2004) — asks whether $c_1(G)$, the least distortion of an embedding of $d_G$ into $L_1$, is bounded by a universal constant for all planar $G$. Equivalently, the multi-commodity flow-cut gap of planar graphs is conjectured to be $O(1)$. The best known bounds have not moved in decades: Rao's $O(\sqrt{\log n})$ upper bound (1999) and the lower bound of 2 (Lee and Raghavendra, 2010), and even the case of planar graphs of treewidth 3 is open. Sidiropoulos (FOCS 2013), the source paper, resolved the special case of non-positively curved planar metrics, later strengthened by Chalopin, Chepoi and Naves (2015) to an isometric embedding of Busemann surfaces; a 2025 journal version by Filtser confirms the general conjecture remains open.

Background

An $n$-vertex weighted graph $G$ induces a finite metric $(V(G), d_G)$, its shortest-path metric. $L_1$ denotes the space of real sequences with norm $\|x\|_1 = \sum_i |x_i|$; a map $f : V \to L_1$ has distortion $\operatorname{dist}(f) = \sup_{x \neq y} \|f(x)-f(y)\|_1 / d_G(x,y) \cdot \sup_{x \neq y} d_G(x,y)/\|f(x)-f(y)\|_1$, and $c_1(G)$ is the minimum distortion over all such maps. Embeddings into $L_1$ matter algorithmically because of the flow-cut connection: Linial, London and Rabinovich (1995), Leighton and Rao (1999), and Aumann and Rabani (1998) showed that the distortion of the best $L_1$-embedding of a graph's metric equals (up to constants) the worst-case ratio between the multi-commodity max-flow and min-cut (the flow-cut gap) of the graph, which controls the approximation ratio of divide-and-conquer algorithms for Sparsest Cut (the problem of partitioning vertices so as to minimize cut capacity relative to the demand separated) and related problems. For general $n$-vertex graphs the gap is $\Theta(\log n)$, so attention turned to restricted families. Okamura and Seymour (1981) proved that demands lying on a single face of a planar graph route exactly (gap 1). Gupta, Newman, Rabinovich and Sinclair (2004) posed two conjectures: the planar embedding conjecture — $c_1(G) = O(1)$ for every planar $G$ — and its generalization, the GNRS conjecture: a graph family has $c_1 = O(1)$ if and only if it forbids some fixed graph as a minor (a minor being obtained from a graph by deleting vertices and edges and contracting edges), which would characterize graphs with constant flow-cut gap. Known positive cases before the source paper: series-parallel graphs, outerplanar graphs (graphs drawable with all vertices on the outer face), and more generally treewidth-2 graphs (the treewidth of a graph measures how tree-like it is: the minimum, over its tree decompositions, of the largest bag size minus one) embed with constant distortion — distortion 2 for treewidth 2, per Chakrabarti, Jaffe, Lee and Vincent (2008) building on Gupta et al., a bound shown optimal by Lee and Raghavendra (2010); $k$-outerplanar graphs (graphs drawable so that peeling off successive outer faces $k$ times removes all vertices) embed into distributions over trees with distortion $2^{O(k)}$ (Chekuri, Gupta, Newman, Rabinovich and Sinclair 2006); and graphs excluding a $K_5 \setminus e$ minor (the complete graph on five vertices with one edge deleted) have constant distortion (Chakrabarti et al. 2008). For arbitrary planar graphs, Rao (1999) proved an $O(\sqrt{\log n})$ upper bound, and Lee and Raghavendra (2010) proved a lower bound of 2. Lee and Sidiropoulos (STOC 2009) showed that the GNRS conjecture is equivalent to the conjunction of the planar embedding conjecture with the k-sum conjecture (constant-distortion embeddability is preserved under $k$-clique-sums, operations gluing two graphs along a shared clique of at most $k$ vertices), for which Lee and Poore (SoCG 2013) obtained only partial progress on the case $k = 2$. Sidiropoulos (FOCS 2013), the source paper, broke new ground geometrically: a planar metric is non-positively curved if it is realizable as points on a simply-connected (planar) surface of non-positive curvature, a CAT(0)-type condition in which geodesics are unique and distance is convex; examples include trees, grids, and subsets of the hyperbolic plane. The paper proved that every non-positively curved planar metric embeds into $L_1$ with a universal constant distortion, and noted (without details, for the infinite case) an extension to simply-connected surfaces of non-positive curvature. Chalopin, Chepoi and Naves (2015) subsequently proved that every Busemann surface — a non-positively curved 2-dimensional surface in the sense of Busemann — embeds isometrically into $L_1$, and that planar graphs that are 1-skeletons (vertex-edge graphs) of planar non-positively curved complexes with regular Euclidean polygon cells embed with distortion at most $2+\pi/2 \approx 3.57$, significantly improving and simplifying Sidiropoulos' result. All of these techniques rely essentially on the convexity of distance, which fails for general planar metrics.

Problem Statement

The planar embedding conjecture (Gupta, Newman, Rabinovich and Sinclair, 2004): does there exist a universal constant $C$ such that every finite planar graph $G$ with positive edge weights, with shortest-path metric $d_G$ on its vertex set, admits a mapping $f : V(G) \to L_1$ (the space of real sequences with norm $\|x\|_1 = \sum_i |x_i|$) satisfying $d_G(x,y)/C \le \|f(x)-f(y)\|_1 \le d_G(x,y)$ for all vertices $x, y$? Equivalently, is $c_1(G) = O(1)$ for every planar graph $G$, where $c_1(G)$ is the minimum distortion of such a mapping; equivalently, is the multi-commodity flow-cut gap of planar graphs bounded by a universal constant? The conjecture must be answered in its full generality — for arbitrary planar metrics, with no restriction to non-positively curved metrics, bounded treewidth (treewidth measuring how tree-like a graph is: the minimum, over tree decompositions, of the largest bag size minus one), bounded outerplanarity, or excluded minors beyond planarity itself — and any resolution settles in particular the case of planar graphs of treewidth 3, which the source paper identifies as open and beyond all known topological methods. The weighted formulation is equivalent to the unweighted one: subdividing each (suitably rescaled) weighted edge into a path of unit-length edges preserves distances between original vertices, and restricting an embedding to a subset of vertices cannot increase its distortion. A positive answer consists of a construction and proof valid for all finite planar graphs; a negative answer consists of an explicit infinite family of planar graphs whose $L_1$-distortion is unbounded, which would also refute the GNRS conjecture restricted to planar graphs and separate planar metrics from $L_1$.

References

1. Anastasios Sidiropoulos. Non-positive Curvature and the Planar Embedding Conjecture. FOCS 2013, pp. 177-186. DOI: 10.1109/focs.2013.27; arXiv:1304.7512, https://arxiv.org/abs/1304.7512.
2. Jérémie Chalopin, Victor Chepoi, and Guyslain Naves. Isometric Embedding of Busemann Surfaces into $L_1$. Discrete & Computational Geometry, 2015. DOI: 10.1007/s00454-014-9643-0; arXiv:1308.3181, https://arxiv.org/abs/1308.3181.
3. Anupam Gupta, Ilan Newman, Yuri Rabinovich, and Alistair Sinclair. Cuts, Trees and $\ell_1$-Embeddings of Graphs. Combinatorica 24(2):233-269, 2004. DOI: 10.1007/s00493-004-0015-x, https://doi.org/10.1007/s00493-004-0015-x.
4. James R. Lee and Anastasios Sidiropoulos. On the geometry of graphs with a forbidden minor. STOC 2009. DOI: 10.1145/1536414.1536450, https://doi.org/10.1145/1536414.1536450.
5. James R. Lee and Daniel Poore. On the 2-sum embedding conjecture. SoCG 2013. DOI: 10.1145/2462356.2492436, https://doi.org/10.1145/2462356.2492436.
6. Satish Rao. Small distortion and volume preserving embeddings for planar and Euclidean metrics. Symposium on Computational Geometry (SoCG) 1999. DOI: 10.1145/304893.304983, https://doi.org/10.1145/304893.304983.
7. James R. Lee and Prasad Raghavendra. Coarse Differentiation and Multi-flows in Planar Graphs. Discrete & Computational Geometry 43(2):346-362, 2010. DOI: 10.1007/s00454-009-9172-4, https://doi.org/10.1007/s00454-009-9172-4.
8. Haruko Okamura and Paul D. Seymour. Multicommodity flows in planar graphs. Journal of Combinatorial Theory, Series B 31(1):75-81, 1981. DOI: 10.1016/S0095-8956(81)80012-3, https://doi.org/10.1016/S0095-8956(81)80012-3.
9. Chandra Chekuri, Anupam Gupta, Ilan Newman, Yuri Rabinovich, and Alistair Sinclair. Embedding k-Outerplanar Graphs into $l_1$. SIAM Journal on Discrete Mathematics 20(1):119-136, 2006. DOI: 10.1137/S0895480102417379, https://doi.org/10.1137/S0895480102417379.
10. Amit Chakrabarti, Alexander Jaffe, James R. Lee, and Justin Vincent. Embeddings of Topological Graphs: Lossy Invariants, Linearization, and 2-Sums. FOCS 2008. DOI: 10.1109/focs.2008.79, https://doi.org/10.1109/focs.2008.79.
11. Arnold Filtser. A Face Cover Perspective to $\ell_1$ Embeddings of Planar Graphs. ACM Transactions on Algorithms 21(1):1-21, 2025 (online November 2024). DOI: 10.1145/3686800; arXiv:1903.02758, https://arxiv.org/abs/1903.02758.
12. Robert Krauthgamer, James R. Lee, and Havana Rika. Flow-Cut Gaps and Face Covers in Planar Graphs. SODA 2019. arXiv:1811.02685, https://arxiv.org/abs/1811.02685.
13. Ken-ichi Kawarabayashi and Anastasios Sidiropoulos. Embeddings of Planar Quasimetrics into Directed $\ell_1$ and Polylogarithmic Approximation for Directed Sparsest-Cut. FOCS 2021. DOI: 10.1109/FOCS52979.2021.00055; arXiv:2111.07974, https://arxiv.org/abs/2111.07974.
14. Ittai Abraham, Arnold Filtser, Anupam Gupta, and Ofer Neiman. Metric Embedding via Shortest Path Decompositions. SIAM Journal on Computing, 2022. DOI: 10.1137/19M1296021, https://doi.org/10.1137/19M1296021.
15. Nikhil Kumar. Multicommodity Flows in Planar Graphs with Demands on Faces. arXiv:2007.01280, https://arxiv.org/abs/2007.01280.
16. Arnold Filtser and Hung Le. Low Treewidth Embeddings of Planar and Minor-Free Metrics. FOCS 2022. DOI: 10.1109/FOCS54457.2022.00105; arXiv:2203.15627, https://arxiv.org/abs/2203.15627.
17. Vincent Cohen-Addad, Hung Le, Marcin Pilipczuk, and Michał Pilipczuk. Planar and Minor-Free Metrics Embed into Metrics of Polylogarithmic Treewidth with Expected Multiplicative Distortion Arbitrarily Close to 1. FOCS 2023. DOI: 10.1109/FOCS57990.2023.00140; arXiv:2304.07268, https://arxiv.org/abs/2304.07268.