Unavoidable Minors for Graphs with Large ℓp -Dimension

Samuel Fiorini, Tony Huynh, Gwenaël Joret, Carole Muller

Research output: Contribution to journalArticleResearchpeer-review


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) → Rk such that dp(ϕ(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 ℓ2-dimension if and only if C has bounded treewidth. In this sense, the ℓ2-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 K4 using the 2-sum operation, or excludes a Möbius ladder with one ‘horizontal edge’ removed.

Original languageEnglish
Pages (from-to)301–343
Number of pages43
JournalDiscrete & Computational Geometry
Issue number1
Publication statusPublished - Jul 2021
Externally publishedYes

Cite this