The Euclidian Distance Matrix Completion Problem

Motivated by the molecular conformation problem, completions of partial Euclidian distance matrices are studied. It is proved that any partial distance matrix with a chordal graph can be completed to a distance matrix. Given any nonchordal graph G, it is shown that there is a partial distance matrix A with graph G such that A does not admit any distance matrix completions. Finally, the connection between distance matrix completions and positive semidefinite completions is outlined.