Pairs distance to ordering?
Apparently, we're given a collection of equations of the form

$$|x_i - x_j| = c_{i,j},$$

where the $c_{i,j}$ are given and $x_1,\dots,x_n$ are the unknowns to solve for.  We want to look for a valid solution that satisfies all of the equations, and where the values of $x_1,\dots,x_n$ are a permutation of $1,2,\dots,n$.

The kind of algorithm to use will probably depend upon how many equations we're given and the structure of the corresponding graph.  However, here is a simple case to start with, to give you some intuition:

Suppose that we are given a complete set of $n(n-1)/2$ equations: i.e., for all $i,j$, we are given $c_{i,j}$.  Then there is a polynomial-time algorithm to recover the $x_i$'s.  Basically, we'll leave $x_1$ as a variable, and we'll try to express every other $x_i$ in terms of $x_1$.  Define $\delta_i$ so that $x_i = x_1 + \delta_i$.  Here's how the algorithm works:


Guess $\delta_2$.  Note that it is either $c_{1,2}$ or $-c_{1,2}$, so there are only two possibilities.
Guess $\delta_3$.  Again, there are only two possibilities: $c_{1,3}$ or $-c_{1,3}$.
Check that $|\delta_2-\delta_3| = c_{2,3}$; if this doesn't hold, discard your current guess.  (This will eliminate $1/2$ of the wrong guesses.)
Guess $\delta_4$; there are only two possibilities.
Check that $|\delta_2-\delta_4| = c_{2,4}$ and $|\delta_3-\delta_4|=c_{3,4}$; if either doesn't hold, discard the current guess.  (This will eliminate at least $1/2$ of the wrong guesses.)
Continue in this way, alternately guessing $\delta_i$ and then checking the equations $|\delta_j-\delta_i|=c_{j,i}$ hold for all $j=2,3,\dots,i-1$.


What's the running time?  The expected running time to list all possible combinations for $\delta_2,\dots,\delta_n$ is $O(n)$.  In particular, at each step, we double the number of combinations we need to consider (since there are two possibilities for the guess), but then we halve the number of combinations we need to consider (since $1/2$ of the wrong guesses can be discarded by virtue of the fact that they violate at least one of the known equations).  Thus the expected number of guesses that remain at the $i$th step is a constant independent of $i$, which implies the running time bound above.

Finally, once you have a combination $\delta_2,\dots,\delta_n$, you can test whether it leads to a viable solution by checking all possible values of $x_1$, inferring the implied values of $x_2,\dots,x_n$ (using the known values for $\delta_2,\dots,\delta_n$), and then checking whether they are a permutation of $1,2,\dots,n$.  Each combination takes $O(n^2)$ time to check, so the overall running time of the algorithm is $O(n^2)$.  This can probably be reduced further, but it's enough to make it already a polynomial-time algorithm.

Now what if we're not given all of the equations?  Then we can apply a similar strategy, but the running time will depend upon the number of equations we're given and the structure of the graph they correspond to.  There's also some degree of freedom in the order that you guess $\delta_i$ values; it's not clear what the optimal strategy is, but probably it will involve looking for small highly-connected regions of the graph and starting with them first.  The best approach might depend upon the specific distribution on problem instances that arises in your practical setting.