Summary:
In the field of Graph Drawing, there is great interest for results regarding
the embedding of a given graph on a grid, mainly due to the applications on the
VLSI circuit design. Moreover, determining whether a graph accepts a
unit-length embedding, i.e., a matching of its vertices and edges to vertices
and edges of a large enough grid, is the same as asking whether the graph is a
subgraph of that grid. We consider the Grid Subgraph problem, in which given a
planar (not necessarily connected) graph G, we need to determine if G is
isomorphic to a subgraph of a large enough grid. We prove that this problem is
NP-complete by employing simple and intuitive gadgets to perform a reduction
from a SAT-variant. In addition we prove that a special case of that problem,
the (k*k)-Grid Subgraph problem, in which the size of the grid is given in the
input, is also NP-complete.
Keywords:
Graph embedding, Orthogonal embedding, Unit-length embedding, VLSI design, NP-completeness
