L1 Embeddings of Graphs of Bounded Treewidth
For every integer , there is a finite constant such that for every finite connected graph admitting a tree decomposition with bags of size at most and every edge-length function , there is a map from into a finite-dimensional real space satisfying for all , where is independent of the number of vertices, the depth of the decomposition, and all ratios of edge lengths.
The proof in Section 7 validly combines Proposition 4.3, Section 5.3, and Proposition 6.1 to obtain the stated finite-dimensional L1 embedding with a constant depending only on k.
“For every integer k >= 2 there is a finite constant Ck >= 1 with the following property. If a finite connected graph G = (V, E) admits a tree decomposition with bags of size at most k, then, for every edge-length function l : E -> (0, infinity), there is a map F from V into a real L1 space such that dG,l(u, v) <= ||F(u) - F(v)||1 <= Ck dG,l(u, v) (u, v in V). The constant is independent of the number of vertices, the depth of the decomposition, and all ratios of edge lengths.” · Show in paper