The excluded minors for isometric realizability in the plane

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₄ 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₁(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.