Adjacency-Preserving 2D Grid Embedding Consider a 2D grid, and a given planar graph $G$ with $\Delta&lt;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&lt;4$ and w/o odd cycles) to be a 2D grid?

Thanks!
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:263–267, 1987.