The Distance Geometry Problem (DGP) asks whether a simple weighted
undirected graph *G* = (*V*,*E*,*d*) can be embedded in a given space so that the
weights of the edges of G, when available, are the same as the distances between
pairs of embedded vertices. The DGP can be discretized when some particular
assumptions are satisfied, which are strongly dependent on the vertex ordering
assigned to *G*. In this work, we focus on the problem of identifying optimal partial
discretization orders for the DGP. The solutions to this problem are in fact
vertex orders that allow for the discretization of the DGP. Moreover, these partial
orders are optimal in the sense that they optimize, at each rank, a given set of objectives
aimed to improve the structure of the search space after the discretization.
This ordering problem is tackled from a theoretical point of view, and some practical
experiences on sets of artificially generated instances, as well as on real-life
instances, are provided.