The excluded minors for isometric realizability in the plane

Samuel Fiorini, Tony Huynh, Gwenaël Joret, Antonios Varvitsiotis

Research output: Contribution to journalArticleResearchpeer-review

2 Citations (Scopus)

Abstract

Let G be a graph and p ϵ [1, oo]. The parameter fp(G) is the least integer k such that for all m and all vectors (rv)vϵV(G) ⊆ Rm, there exist vectors (qv)vϵV(G) ⊆ Rk satisfying ∥v - rw∥p = ∥qv - qw∥p for all vw ϵ E(G). It is easy to check that fp(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 K4 along an edge and then deleting that edge. We also show that the same two graphs are the complete set of excluded minors for f1(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 languageEnglish
Pages (from-to)438-453
Number of pages16
JournalSIAM Journal on Discrete Mathematics
Volume31
Issue number1
DOIs
Publication statusPublished - 1 Jan 2017
Externally publishedYes

Keywords

  • Finite metric spaces
  • Graph minors
  • Isometric embeddings

Cite this