Problem statement in the title is simplified and this question is actually quite open-ended: I have a sparse undirected simple weighted graph $G$ and need to find an injective function $G \rightarrow \mathbb{Z}$ such that connected nodes are nearby, with nodes connected by edges with higher weight placed closer together.
My gut instinct is to frame this as an optimization problem: Numbering each node a solution could be obtained as a minimizer for an appropriate objective function $\phi:\mathbb{Z}^n \rightarrow \mathbb{Z}$, where the $j$-th input coordinate represents the location of the $j$-th node. I have some ideas around how to construct a reasonable objective function, using the edge weights connecting nodes and their distances in $\mathbb{Z}^n$, but no ideas how to minimize it since my experience is entirely with convex programming.
Any thoughts on how to approach this problem would be welcome. If you need more details, then I can try to provide them in an edit.
Thanks a bunch everybody!