## Unavoidable minors for graphs with large $$\ell_p$$-dimension

Algorithms Seminars
June 11, 2019 2:00 pm

Abstract: A metric graph is a pair $$(G,d)$$, where $$G$$ is a graph and $$d:E(G) \to\mathbb{R}_{\geq0}$$ is a distance function. Let $$p \in [1,\infty]$$ be fixed. An isometric embedding of the metric graph $$(G,d)$$ in $$\ell_p^k = (\mathbb{R}^k, d_p)$$ is a map $$\phi : V(G) \to \mathbb{R}^k$$ such that $$d_p(\phi(v), \phi(w)) = d(vw)$$ for all edges $$vw\in E(G)$$. The $$\ell_p$$-dimension of $$G$$ is the least integer $$k$$ such that there exists an isometric embedding of $$(G,d)$$ in $$\ell_p^k$$ for all distance functions $$d$$ such that $$(G,d)$$ has an isometric embedding in $$\ell_p^K$$ for some $$K$$.

It is easy to show that $$\ell_p$$-dimension is a minor-monotone property. We characterize the minor-closed graph classes $$\mathcal{C}$$ with bounded $$\ell_p$$-dimension, for $$p \in \{2,\infty\}$$. For $$p=2$$, we give a simple proof that $$\mathcal{C}$$ has bounded $$\ell_2$$-dimension if and only if $$\mathcal{C}$$ has bounded treewidth. In this sense, the $$\ell_2$$-dimension of a graph is ‘tied’ to its treewidth. For $$p=\infty$$, the situation is completely different. Our main result states that a minor-closed class $$\mathcal{C}$$ has bounded $$\ell_\infty$$-dimension if and only if $$\mathcal{C}$$ excludes a graph obtained by joining copies of $$K_4$$ using the 2-sum operation, or excludes a Möbius ladder with one ‘horizontal edge’ removed.
This is joint work with Samuel Fiorini, Gwenaël Joret, and Carole Muller. Preprint available at https://arxiv.org/abs/1904.02951.