We present an efficient algorithm to find a realization of a (full) n×. n squared Euclidean distance matrix in the smallest possible dimension. Most existing algorithms work in a given dimension: most of these can be transformed to an algorithm to find the minimum dimension, but gain a logarithmic factor of n in their worst-case running time. Our algorithm performs cubically in n (and linearly when the dimension is fixed, which happens in most applications). © 2015 Elsevier B.V.50 397402ANR-10-BINF-03-08, ANR, Agence Nationale de la RechercheDattorro, J., Convex Optimization and Euclidean Distance Geometry (2005), Meboo, Palo AltoLiberti, L., Lavor, C., Maculan, N., Mucherino, A., Euclidean distance geometry and applications (2014) SIAM Review, 56, pp. 3-69Householder, A.S., Young, G., Discussion of a set of points in terms of their mutual distances (1938) Psychometrika, 3, pp. 19-22Lavor, C., On generating instances for the molecular distance geometry problem (2006) Global optimization, pp. 405-414. , Springer USMoré, J.J., Wu, Z., Global continuation for distance geometry problems (1997) SIAM Journal on Optimization, 7, pp. 814-836Dong, Q., Wu, Z., A linear-time algorithm for solving the molecular distance geometry problem with exact inter-atomic distances (2002) Journal of Global Optimization, 22, pp. 365-375Scheraga, H.A., Sippl, M.J., Solution of the embedding problem and decomposition of symmetric matrices (1985) Proceedings of the National Academy of Sciences, 82, pp. 2197-2201Barvinok, A., Problems of Distance Geometry and convex properties of quadratic maps (1995) Discrete and Computational Geometry, 13, pp. 189-202