Complexity of Labeled Graph Homomorphism

The following recreational math problem has been floating around work:

We're given an $m \times n$ grid ($m,n$ positive integers). We wish to label the elements of the grid with letters so that we can spell out the name of the nine (this originated before Pluto was demoted) planets, where allowable neighbors of a point in the grid are those points on the grid which are immediately up, down, left or right (provided they exist). The challenge was to find the grid of the smallest area ($mn$) which allowed such a labeling. The best answer given was for a $4 \times 8$ grid. Since it's clear that if an $m \times n$ grid is possible then so is an $(m+1) \times n$ and $m \times (n+1)$ grid, we're really interested in finding those pairs $(m,n)$ which are maximally impossible. It appears that this is the set $\{ (5,6), (6,5), (4,7),(7,4) \}$, but both of these impossibility results come from a very long running backtrack program. It would be nicer if there was a better proof.

So, stepping back from the specific problem we see that it's an instance of the following problem:

We're given $G, H$ undirected graphs, with the vertices of $G$ labeled: $l(v)$ is the label of $v \in V(G)$. We wish to find a homomorphism $f :G \rightarrow H$ (i.e. a map from $f: V(G) \rightarrow V(H)$ such that if $(v,v') \in E(G)$ then $(f(v),f(v')) \in E(H)$) and a labeling $l$ of vertices of $H$ such that $l(f(v)) = l(v)$ for all $v \in V(G)$. In our original problem, $G$ is the disjoint union of 9 paths, labeled with the spelling of planets' names, and $H$ is the $m \times n$ grid graph. I've found that there has been some work on the homomorphism existence problem for graphs, which is a generalization of graph coloring (take $H=K_n$ the complete graph on $n$ vertices. Existence of a homomorphism $f : G \rightarrow H$ is the same as an $n$-coloring of $G$). But there is a dichotomy: if $H$ is bipartite, then this is easy (since it becomes the same as determining whether or not $G$ is bipartite), and if not, it's NP-complete. The graphs in the above problem are both bipartite, but the labeling requirement appears to make it much more difficult. So, does anyone know about the generalization that I've given which requires a certain labeling?

-
Why not 3x10 as a candidate? Gerhard "Ask Me About System Design" Paseman, 2012.04.11 –  Gerhard Paseman Apr 11 '12 at 18:01
@Gerhard: You're right. It looks like (3,11) is also a maximal impossible. –  Victor Miller Apr 16 '12 at 22:34

Do you know the shortest superstring problem? Given a set of strings $S$ find the shortest string $\alpha$ s.t. each string in $S$ is a substring of $\alpha$. This problem is NP-hard.