[tberxdfm] Mashing points into grids

Given a graph of M*N nodes and arbitrary edges, assign the nodes to an MxN rectangular array of grid points arranged in a square lattice, placing one node per grid point.  Compute a score of the assignment: model the graph edges as springs having potential energy d^2, or (perhaps more accurately) (d-1)^2 where d is the length of an edge and 1 is the distance between adjacent grid points.  Find an assignment of nodes to grid positions that minimizes total energy of the edges.

I think this is a well studied optimization problem: graph layout.  Simulated annealing is one way.  An operation possible for this kind of combinatorial optimization is to pick up one node, slide a line of nodes over by 1 grid unit toward where the first node was (filling the spot where it used to be), and place the first node into the empty spot that opens up at the end of the line.  Previously, relocating large blocks of nodes in one operation.  General idea is to mostly preserve local neighborhoods of nodes.

Consider an input graph which is the connectivity graph of a grid in a different number of dimensions.  For example, map (n^2)^3 points of a 3D grid in a cube into a (n^3)^2 square.  Or start with a 4D grid and assign to a 2D or 3D grid.  This might help illustrate the geometry of 4D, what's close to what.  Original motivation: depict 4D cellular automata on a 2D screen.

If we start with 2D and go down to 1D, then trace in order the nodes of the lowest energy 1D configuration back in 2D, do we get something that looks like a Hilbert curve?  Should we?  We might need to adjust the energy function.

Sophistications:

Destination space is a grid not on a rectangle but on a flat torus.  Distance is the minimum of the several possible ways to get between grid points.

In general, input can be any graph.  Output must be a graph embedded in a space in which we can calculate distances, i.e., a metric space.

More grid points, maybe an infinite grid, than input nodes.  Optimization algorithm chooses a subset of grid points, probably a compact blob.

If the input and output are the same grid (nodes permuted), can the algorithm recover the input grid (modulo reflections and rotations)?