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.