<p>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:</p>

<p>S. Bhatt and S. Cosmodakis. The complexity of minimizing wire lengths in VLSI layouts.
<em>Inform. Proc. Lett.</em> 25:263–267, 1987.</p>

CC BY-SA 3.0
2013-03-27T05:39:01.547Z
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.
Alireza Shafaei
CC BY-SA 3.0
2013-03-27T07:07:05.513Z
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)$.
David Eppstein
CC BY-SA 3.0
2013-03-27T04:17:52.420Z
2013-03-27T04:17:52.420Z
David Eppstein
<p>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. </p>

<p>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?</p>

<p>Thanks!</p>

<graph-theory><cg.comp-geom><embeddings>
Adjacency-Preserving 2D Grid Embedding
Alireza Shafaei
# Adjacency-Preserving 2D Grid Embedding

(Asked by: username_0 on 2013-03-27)

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!

**Tags:** graph-theory, cg.comp-geom, embeddings


---

## 1 answers

### Answer by username_1 on 2013-03-27. Score: 8 | Accepted answer

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.

> **Comments:**
> **username_0**: 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.  
> **username_1**: 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)$.  

---

