Given a graph G=(V=[n],E), its {\em Gram dimension} Undefined control sequence \GD is the smallest integer r≥1 such that, for any n×n positive semidefinite matrix X, there exist vectors Undefined control sequence \oR (i∈V) satisfying Xij=pTipj for all ij∈V∪E.

The class of graphs with Gram dimension at most r is closed under taking minors and clique sums. Clearly, Kr+1 is a minimal forbidden minor for membership in this class.We show that this is the only minimal forbidden minor for r≤3 while, for r=4, there are two minimal forbidden minors: the complete graph K5 and the octahedron K2,2,2.These results are closely related to the characterization of Belk and Connelly (2007) for the class of d-realizable graphs with d≤3. Recall that G is {\em d-realizable} if, for any vectors ui (i∈V), there exist other vectors Undefined control sequence \oR(i∈V) satisfying ∥ui−uj∥2=∥vi−vj∥2 for all ij∈E; that is, for any n×n Euclidean distance matrix, the distances corresponding to edges can be realized in Undefined control sequence \oR.Denoting by Undefined control sequence \ED the smallest integer d such that G is d-realizable,

the two parameters are related by Undefined control sequence \GD, where ∇G is the one-node suspension of G. Moreover,they satisfy: Undefined control sequence \GD and Undefined control sequence \ED. Hence, Undefined control sequence \GD, so that our results imply those of Belk and Connelly.

Joint work with Antonis Varvitsiotis (CWI, Amsterdam).