Unavoidable Minors for Graphs with Large ℓ_p -Dimension

A metric graph is a pair (G, d), where G is a graph and d: E(G) → R_{≥ 0} is a distance function. Let p∈ [1 , ∞] be fixed. An isometric embedding of the metric graph (G, d) in ℓpk=(Rk,dp) is a map ϕ: V(G) → R^k such that d_p(ϕ(v) , ϕ(w)) = d(vw) for all edges vw∈ E(G). The ℓ_p-dimension of G is the least integer k such that there exists an isometric embedding of (G, d) in ℓpk for all distance functions d such that (G, d) has an isometric embedding in ℓpK for some K. It is easy to show that ℓ_p-dimension is a minor-monotone property. In this paper, we characterize the minor-closed graph classes C with bounded ℓ_p-dimension, for p∈ { 2 , ∞}. For p= 2 , we give a simple proof that C has bounded ℓ₂-dimension if and only if C has bounded treewidth. In this sense, the ℓ₂-dimension of a graph is ‘tied’ to its treewidth. For p= ∞, the situation is completely different. Our main result states that a minor-closed class C has bounded ℓ_∞-dimension if and only if C excludes a graph obtained by joining copies of K₄ using the 2-sum operation, or excludes a Möbius ladder with one ‘horizontal edge’ removed.