Cuts, trees and \(\ell_1\)-embeddings of graphs (Q705742)

It is investigated when the metric obtained by associating non-negative weights to the edges of a graph can be embedded within constant distortion into an \(\ell_1\)-space. Such an embedding with no distortion, i.e., an isometric embedding, exists if and only if the graph has no \(K_{2,3}\) minor. The optimal distortion \(c_1(G)\) is equal to the worst possible gap attained by a multicommodity flow problem on \(G\). It is conjectured that \(c_1(G)\) is bounded for any nontrivial minor-closed family of graphs. If \(G\) is series-parallel (or even if it has treewidth 2), then \(c_1(G)<14\) and an embedding can be found in polynomial time. Further, \(c_1(G)=O(\log \chi(G))\) with \(\chi(G)\) the Euler-characteristic of \(G\). The embeddings are determined via distributions over cuts and trees, respectively. In the tree case, lower bounds are given, as well.