## Abstract

Let G be a graph and p ϵ [1, oo]. The parameter f_{p}(G) is the least integer k such that for all m and all vectors (r_{v})_{vϵV(G)} ⊆ R^{m}, there exist vectors (q_{v})_{vϵV(G)} ⊆ R^{k} satisfying ∥_{v} - r_{w}∥p = ∥q_{v} - q_{w}∥p for all vw ϵ E(G). It is easy to check that f_{p}(G) is always finite and that it is minor monotone. By the graph minor theorem of Robertson and Seymour [J. Combin. Theory Ser. B, 92(2004), pp. 325-357], there are a finite number of excluded minors for the property fp(G) ≤ k. In this paper, we determine the complete set of excluded minors for f_{∞}(G) ≤ 2. The two excluded minors are the wheel on five vertices and the graph obtained by gluing two copies of K_{4} along an edge and then deleting that edge. We also show that the same two graphs are the complete set of excluded minors for f_{1}(G) ≤ 2. In addition, we give a family of examples that show that f_{∞}, is unbounded on the class of planar graphs and f_{∞}, is not bounded as a function of tree-width.

Original language | English |
---|---|

Pages (from-to) | 438-453 |

Number of pages | 16 |

Journal | SIAM Journal on Discrete Mathematics |

Volume | 31 |

Issue number | 1 |

DOIs | |

Publication status | Published - 1 Jan 2017 |

Externally published | Yes |

## Keywords

- Finite metric spaces
- Graph minors
- Isometric embeddings