A \emph{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 \emph{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 \emph{$\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. In this paper, 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\"obius ladder with one horizontal edge' removed.

Unavoidable minors for graphs with large l_p-dimension / Fiorini, S.; Huynh, T.; Joret, G.; Muller, C.. - In: DISCRETE AND COMPUTATIONAL GEOMETRY. - ISSN 1432-0444. - (2019).

### Unavoidable minors for graphs with large l_p-dimension

#### Abstract

A \emph{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 \emph{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 \emph{$\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. In this paper, 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\"obius ladder with one horizontal edge' removed.
##### Scheda breve Scheda completa
2019
graphs, metric spaces
01 Pubblicazione su rivista::01a Articolo in rivista
Unavoidable minors for graphs with large l_p-dimension / Fiorini, S.; Huynh, T.; Joret, G.; Muller, C.. - In: DISCRETE AND COMPUTATIONAL GEOMETRY. - ISSN 1432-0444. - (2019).
File allegati a questo prodotto
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/1696418
##### Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

• ND
• ND
• ND