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!

• Thanks David. If run-time is not an issue (say for small problem sizes, e.g., a graph with 6 nodes), is there an algorithm that can decide whether the given graph is embeddable into the 2D grid with unit length edges? Obviously, Any graph with $\Delta<3$ and without odd cycles can be embedded into a 2D grid while preserving the adjacency of nodes. Are there any other conditions like this that can specify a subset of graphs that are adjacency-preserving grid-embeddable. Mar 27 '13 at 5:39
• If run time is not an issue, find a spanning tree, choose one of three orientations for each edge (the fourth, the orientation that would overlap the parent edge, is forbidden) in time $O(3^n)$, for each choice traverse the tree to turn that choice into positions for all the vertices, and check whether the vertices aren't on top of each other and the remaining edges have endpoints at unit distance from each other. Total time $O(n3^n)$. Mar 27 '13 at 7:07