Cuts, trees and _1-embeddings of graphs
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.
- From cuts to \(\mathbb{R}\)-trees
- The tree of cuts and minimal \(k\)-connected graphs
- Cutpoints on trees and spherically symmetric graphs
- On embedding graphs in trees
- Cuts in undirected graphs. I
- Embeddings of graphs of fixed treewidth and bounded degree
- Cuts in undirected graphs. II
- On the cut dimension of a graph
- Embedding complete multipartite graphs into certain trees
- The \({l_1}\)-embeddability of trees, unicyclic graphs and their line graphs
- Cuts, matrix completions and graph rigidity
- An introduction to the Ribe program
- Maximum gradient embeddings and monotone clustering
- Analysis on Laakso graphs with application to the structure of transportation cost spaces
- Isometric structure of transportation cost spaces on finite metric spaces
- A 2-approximation for the bounded treewidth sparsest cut problem in \textsf{FPT} Time
- Isometric embedding of Busemann surfaces into L₁
- Nonexistence of embeddings with uniformly bounded distortions of Laakso graphs into diamond graphs
- On the geometry of the countably branching diamond graphs
- Pathwidth, trees, and random embeddings
- Non-greedy online Steiner trees on outerplanar graphs
- Metric embeddings of Laakso graphs into Banach spaces
- Non-greedy online Steiner trees on outerplanar graphs
- A tight upper bound on the probabilistic embedding of series-parallel graphs
- DIAMOND GRAPHS AND SUPER-REFLEXIVITY
- On average distortion of embedding metrics into the line and into l₁
- Hard Metrics from Cayley Graphs of Abelian Groups
- Markov type and threshold embeddings
- Embedding Bounded Bandwidth Graphs into ℓ1
- The cut cone,L1 embeddability, complexity, and multicommodity flows
- Low-distortion embeddings of graphs with large girth
- A coding of bundle graphs and their embeddings into Banach spaces
- Distortion of embeddings of binary trees into diamond graphs
- A doubling subset of \(L_p\) for \(p>2\) that is inherently infinite dimensional
- Metric characterizations of superreflexivity in terms of word hyperbolic groups and finite graphs
- FPT algorithms for embedding into low complexity graphic metrics
- Metric Embedding via Shortest Path Decompositions
- Lipschitz-free spaces on finite metric spaces
- A face cover perspective to ℓ1 embeddings of planar graphs
- On the geometry of graphs with a forbidden minor
- On the 2-sum embedding conjecture
- Algorithms – ESA 2004
- On the impossibility of dimension reduction for doubling subsets of \(\ell_{p}\)
- An exact algorithm for minimum distortion embedding
- On multiplicative \(\lambda\)-approximations and some geometric applications
- Slightly superexponential parameterized problems
- Maximum weight disjoint paths in outerplanar graphs via single-tree cut approximators
- Maximum weight disjoint paths in outerplanar graphs via single-tree cut approximators
- Stochastic approximation of lamplighter metrics
- 𝐿₁-distortion of Wasserstein metrics: A tale of two dimensions
- Cut-sufficient directed 2-commodity multiflow topologies
- scientific article; zbMATH DE number 7765399 (Why is no real title available?)
- \(k\)-outerplanar graphs, planar duality, and low stretch spanning trees
- A 2-approximation for the bounded treewidth sparsest cut problem in \textsf{FPT} time
- Stochastic embeddings of graphs into trees
- An approximate generalization of the Okamura-Seymour theorem
- Optimal padded decomposition for bounded treewidth graphs
- O(1) Steiner point removal in series-parallel graphs
- Cut-sufficient directed 2-commodity multiflow topologies
- A face cover perspective to _1 embeddings of planar graphs
- Approximating sparsest cut in low-treewidth graphs via combinatorial diameter
- On sparse covers of minor free graphs, low dimensional metric embeddings, and other applications
- Improved lower bounds on multiflow-multicut gaps
- Metric spaces with small rough angles and the rectifiability of rough self-contracted curves
- A note on multiflows and treewidth
- Coarse differentiation and multi-flows in planar graphs
- Randomly removing \(g\) handles at once
This page was built for publication: Cuts, trees and \(\ell_1\)-embeddings of graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q705742)
