Consider a 2D grid, and a given planar graph $G$ with $\Delta<4$ (max node degree) and without odd cycles. What conditions should $G$ satisfy so that when it is mapped (or embedded) into the 2D grid, the adjacency of the nodes is maintained (i.e., all adjacent nodes in $G$ remain adjacent in the 2D grid). Accordingly, after embedding of $G$ in the 2D grid, the shortest path distance between adjacent nodes is still 1. The alternative question is what is the condition for a given planar graph (with $\Delta<4$ and w/o odd cycles) to be a 2D grid?Thanks!
Adjacency-Preserving 2D Grid Embedding
graph theory;cg.comp geom;embeddings
Embedding planar graphs (with max degree four) in an adjacency-preserving way onto a grid is NP-complete, meaning that there's unlikely to be simple necessary and sufficient conditions. Actually that's still true even for embedding trees into a grid. See:S. Bhatt and S. Cosmodakis. The complexity of minimizing wire lengths in VLSI layouts.Inform. Proc. Lett. 25:263267, 1987.