4
$\begingroup$

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!

Improve this question
$\endgroup$

1 Answer 1

Reset to default
8
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Alireza Shafaei
    Mar 27, 2013 at 5:39
  • 6
    $\begingroup$ 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)$. $\endgroup$
    – David Eppstein
    Mar 27, 2013 at 7:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.