Finding grid embeddings with bounded maximum edge length is NP-complete
Hans L. Bodlaender · 1985
The following problem is proven to be NP-complete for every fixed k2: Given a graph G=(VjE) is there an injectlye mapping f of V to a two-dimensional grid, such that for every edge (xy)eEj the dis- tance between f(x) and f(y) in the grid is at most k The same problem is also NP-complete for mappings to d-dimensional grids with d3, for all fixed kl] 1]