TY - JOUR

T1 - Unavoidable Minors for Graphs with Large ℓp -Dimension

AU - Fiorini, Samuel

AU - Huynh, Tony

AU - Joret, Gwenaël

AU - Muller, Carole

N1 - Funding Information:
S. Fiorini and T. Huynh are supported by ERC Consolidator Grant 615640-ForEFront. G. Joret is supported by an ARC Grant from the Wallonia-Brussels Federation of Belgium. C. Muller is supported by the Luxembourg National Research Fund (FNR) Grant No. 11628910.
Publisher Copyright:
© 2021, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.
Copyright:
Copyright 2021 Elsevier B.V., All rights reserved.

PY - 2021/7

Y1 - 2021/7

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85106530798&partnerID=8YFLogxK

U2 - 10.1007/s00454-021-00285-5

DO - 10.1007/s00454-021-00285-5

M3 - Article

AN - SCOPUS:85106530798

VL - 66

SP - 301

EP - 343

JO - Discrete & Computational Geometry

JF - Discrete & Computational Geometry

SN - 0179-5376

IS - 1

ER -