The approach in the paper I linked is different. We break the graph into overlapping smaller subgraphs, so small that they can only be embedded in one way (that's called rigidity) and then "stitch" them together consistently. The "stitching" is done with a very handy trick involving eigenvectors of sparse matrices. But the point I want to emphasize here is that you have to look at the small scale, and let all the little patches embed themselves as they like, before trying to reconcile them globally.

Forget the context for a moment - this note is a very general, very useful observation!