The GNRS conjecture for minor-excluding graph families: the planar embedding and $k$-sum conjectures

A graph family excludes a minor if some fixed graph cannot be obtained from any member by deleting edges, vertices, or contracting edges. The Gupta–Newman–Rabinovich–Sinclair (GNRS) conjecture predicts that a family of finite graphs has uniformly bounded $L_1$-distortion of its shortest-path metrics if and only if it excludes some minor. Lee and Sidiropoulos (STOC 2009) proved this conjecture equivalent to the conjunction of two concrete open problems: (A) the planar embedding conjecture, that every shortest-path metric of a planar graph embeds into $L_1$ with distortion bounded by a universal constant; and (B) the $k$-sum conjecture, that for every graph family $\mathcal{F}$ and every $k$, closure under $k$-clique sums preserves boundedness of the $L_1$-distortion. Both components — and hence the GNRS conjecture itself and the bounded-treewidth special case — remain open as of 2026: the best upper bound for planar graphs is $O(\sqrt{\log n})$ (Rao), the best lower bound is 2 (Lee–Raghavendra), and the $k$-sum conjecture is open even for $k=2$ beyond finite families (Lee–Poore settled the finite-family case).

Background

For a (nonnegatively) edge-weighted graph $G$, the shortest-path metric $d_G$ assigns to each pair of vertices the minimum total weight of a path joining them. An embedding $f$ of a finite metric $(X,d)$ into $L_1$ (the space of Lebesgue-integrable functions with the norm $\|g\|_1=\int|g|$, whose finite-dimensional structure is that of conical combinations of cut metrics) has distortion at most $D$ if $d(x,y)\le\|f(x)-f(y)\|_1\le D\cdot d(x,y)$ for all $x,y$; the least such $D$ is written $c_1(X)$, and for a family $\mathcal{F}$ of graphs one writes $c_1(\mathcal{F})=\sup_{G\in\mathcal{F}} c_1(G)$. A graph $H$ is a minor of $G$ if $H$ can be obtained from $G$ by deleting vertices, deleting edges, and contracting edges; $\mathcal{F}$ excludes (forbids) a minor if some fixed $H$ is a minor of no member of $\mathcal{F}$. Planar graphs, bounded-treewidth graphs, and bounded-genus graphs are the standard examples. Here treewidth is the standard width measure of a tree decomposition (bags of vertices of size at most $k+1$ arranged in a tree, with each vertex covered by a connected set of bags and each edge covered by some bag); graphs of treewidth at most $k$ are exactly the graphs assembled from copies of the complete graph $K_{k+1}$ by gluing along cliques of size at most $k$ and possibly deleting the edges of the glued cliques (clique sums). For a family $\mathcal{F}$ and an integer $k$, $\oplus_k\mathcal{F}$ denotes the closure of $\mathcal{F}$ under the $k$-clique sum operation: given $G_1,G_2\in\mathcal{F}$ (or already constructed graphs), identify a clique of size at most $k$ in each, glue the two graphs along it, and possibly delete the edges of the glued clique. The subject has an algorithmic anchor: a theorem of Linial, London, and Rabinovich (1995) and of Gupta–Newman–Rabinovich–Sinclair identifies $c_1(G)$ with the multi-commodity flow-cut gap of $G$ (the worst ratio between the sparsest cut and the concurrent multi-commodity flow), so constant-distortion $L_1$-embeddability of a family is exactly an approximate max-flow/min-cut theorem for that family. Since general graphs require $\Theta(\log n)$ distortion, the natural sharp question is which structured families achieve a constant. Okamura and Seymour (1981) proved that terminals lying on a single face of a planar graph embed isometrically into $L_1$. Gupta, Newman, Rabinovich, and Sinclair (1999/2004) proved $c_1=O(1)$ for outerplanar and series-parallel graphs (treewidth at most 2, the case $\mathcal{F}=\{K_3\}$ under 2-sums) and posed the GNRS conjecture: $c_1(\mathcal{F})<\infty$ if and only if $\mathcal{F}$ forbids some minor. The easy direction (unbounded-distortion expander-type families exclude no minor) was already known; the open content is that minor exclusion forces bounded distortion. Chakrabarti, Jaffe, Lee, and Vincent (2008) sharpened the treewidth-2 bound to distortion 2 (tight by Lee–Raghavendra's lower bound) and confirmed the 2-sum case for $\mathcal{F}=\{K_4\}$; Chekuri, Gupta, Newman, Rabinovich, and Sinclair (2006) settled $k$-outerplanar graphs. Lee and Sidiropoulos (STOC 2009) proved that the GNRS conjecture is equivalent to the conjunction of two manifestly simpler conjectures: (A) the planar embedding conjecture — $c_1(\mathrm{Planar})=O(1)$, i.e. some universal constant bounds the $L_1$-distortion of every planar-graph metric; and (B) the $k$-sum conjecture — for every family $\mathcal{F}$ and every $k\in\mathbb{N}$, $c_1(\mathcal{F})=O(1)$ if and only if $c_1(\oplus_k\mathcal{F})=O(1)$. The reduction flows through the Robertson–Seymour graph minor structure theorem, by which every minor-excluding family is built from bounded-genus pieces by bounded-size clique sums, and genus reduces to the planar case. The case $k=1$ is folklore; $k=2$ was already open. Since treewidth-$k$ graphs are the $k$-sum closure of the single family $\{K_{k+1}\}$, the conjecture subsumes the question of whether $c_1(\mathrm{Treewidth}(k))$ is bounded for every fixed $k$ — known for $k\le 2$, open for $k\ge 3$.

Problem Statement

Settle the two open conjectures to which Lee and Sidiropoulos (STOC 2009) reduced the GNRS conjecture, in their full generality:

(A) Planar embedding conjecture. Determine whether there exists a universal constant $C$ such that every shortest-path metric of every finite edge-weighted planar graph admits an embedding into $L_1$ with distortion at most $C$; equivalently, whether $c_1(\mathrm{Planar})=O(1)$. A negative answer must exhibit, with proof, an infinite family of planar graphs whose $L_1$-distortion is unbounded (a single finite graph cannot refute the uniform statement).

(B) $k$-sum conjecture. For every integer $k\in\mathbb{N}$ and every family $\mathcal{F}$ of finite graphs, determine whether $c_1(\mathcal{F})=O(1)$ holds if and only if $c_1(\oplus_k\mathcal{F})=O(1)$, where $\oplus_k\mathcal{F}$ is the closure of $\mathcal{F}$ under $k$-clique sums. The case $k=1$ is known (folklore); the problem includes the case $k=2$ for arbitrary (in particular infinite) families $\mathcal{F}$, and all $k\ge 3$. The sub-case $\mathcal{F}=\{K_{k+1}\}$ — whether $c_1(\mathrm{Treewidth}(k))$ is bounded for every fixed $k$ — is part of (B) and must not be dropped.

By the Lee–Sidiropoulos equivalence, a complete positive answer to both (A) and (B) is exactly a proof of the GNRS conjecture (bounded $L_1$-distortion characterizes minor-excluding graph families); a refutation of either component refutes the GNRS conjecture. Note that in (B) the implication $c_1(\oplus_k\mathcal{F})=O(1)\Rightarrow c_1(\mathcal{F})=O(1)$ is immediate from $\mathcal{F}\subseteq\oplus_k\mathcal{F}$, so the open content of (B) is the forward direction $c_1(\mathcal{F})=O(1)\Rightarrow c_1(\oplus_k\mathcal{F})=O(1)$ for every $k$ and every family $\mathcal{F}$; resolving a single component, or only a trivial direction of (B), does not settle the stated problem.

References

1. James R. Lee, Anastasios Sidiropoulos. On the geometry of graphs with a forbidden minor. Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC '09), pp. 245–254, ACM, 2009. DOI: 10.1145/1536414.1536450. URL: https://doi.org/10.1145/1536414.1536450
2. Anupam Gupta, Ilan Newman, Yuri Rabinovich, Alistair Sinclair. Cuts, trees and $\ell_1$-embeddings of graphs. Combinatorica 24(2):233–269, 2004. DOI: 10.1007/s00493-004-0015-x. URL: https://doi.org/10.1007/s00493-004-0015-x (preliminary version: FOCS 1999, DOI: 10.1109/sffcs.1999.814611)
3. Nathan Linial, Eran London, Yuri Rabinovich. The geometry of graphs and some of its algorithmic applications. Combinatorica 15(2):215–245, 1995. DOI: 10.1007/bf01200757. URL: https://doi.org/10.1007/bf01200757
4. Haruko Okamura, P. 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. URL: https://doi.org/10.1016/s0095-8956(81)80012-3
5. Satish Rao. Small distortion and volume preserving embeddings for planar and Euclidean metrics. Proceedings of the Fifteenth Annual Symposium on Computational Geometry (SoCG '99), pp. 300–306, ACM, 1999. DOI: 10.1145/304893.304983. URL: https://doi.org/10.1145/304893.304983
6. Amit Chakrabarti, Alexander Jaffe, James R. Lee, Justin Vincent. Embeddings of topological graphs: lossy invariants, linearization, and 2-sums. 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2008), pp. 761–770, IEEE, 2008. DOI: 10.1109/FOCS.2008.79. URL: https://doi.org/10.1109/FOCS.2008.79
7. Chandra Chekuri, Anupam Gupta, Ilan Newman, Yuri Rabinovich, Alistair Sinclair. Embedding $k$-outerplanar graphs into $\ell_1$. SIAM Journal on Discrete Mathematics 20(1):119–136, 2006. DOI: 10.1137/s0895480102417379. URL: https://doi.org/10.1137/s0895480102417379
8. James R. Lee, 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. URL: https://doi.org/10.1007/s00454-009-9172-4 (arXiv:0804.1573)
9. James R. Lee, Anastasios Sidiropoulos. Pathwidth, trees, and random embeddings. Combinatorica 33(3):349–374, 2013. DOI: 10.1007/s00493-013-2685-8. URL: https://doi.org/10.1007/s00493-013-2685-8 (arXiv:0910.1409)
10. Anastasios Sidiropoulos. Non-positive curvature, and the planar embedding conjecture. Preprint, 2013. arXiv:1304.7512. URL: https://arxiv.org/abs/1304.7512
11. James R. Lee, Daniel E. Poore. On the 2-sum embedding conjecture. Proceedings of the 29th Annual Symposium on Computational Geometry (SoCG 2013), pp. 197–206, ACM, 2013. DOI: 10.1145/2462356.2492436. URL: https://doi.org/10.1145/2462356.2492436
12. Jérémie Chalopin, Victor Chepoi, Guyslain Naves. Isometric embedding of Busemann surfaces into $L_1$. Discrete & Computational Geometry 53(1):16–37, 2015. DOI: 10.1007/s00454-014-9643-0. URL: https://doi.org/10.1007/s00454-014-9643-0 (arXiv:1308.3181)
13. Ittai Abraham, Arnold Filtser, Anupam Gupta, Ofer Neiman. Metric embedding via shortest path decompositions. Preprint, 2017 (preliminary version STOC 2018). arXiv:1708.04073. URL: https://arxiv.org/abs/1708.04073
14. Arnold Filtser. A face cover perspective to $\ell_1$ embeddings of planar graphs. Preprint, 2019. arXiv:1903.02758. URL: https://arxiv.org/abs/1903.02758
15. Vincent Cohen-Addad, Hung Le, Marcin Pilipczuk, Michał Pilipczuk. Planar and minor-free metrics embed into metrics of polylogarithmic treewidth with expected multiplicative distortion arbitrarily close to 1. 64th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2023). DOI: 10.1109/focs57990.2023.00140. URL: https://doi.org/10.1109/focs57990.2023.00140 (arXiv:2304.07268)
16. Hung Le, Hector Tierno, Shuang Yang. Planar embedding of Okamura–Seymour quasimetrics in polynomial time with an application to distributed SSSP. Preprint, 2026. arXiv:2606.31192. URL: https://arxiv.org/abs/2606.31192