  In this paper, we give new, tight subexponential lower bounds for a number of
graph embedding problems. We introduce two related combinatorial problems,
which we call String Crafting and Orthogonal Vector crafting, and show that
these cannot be solved in time $2^{o(|s|/\log{|s|})}$, unless the Exponential
Time Hypothesis fails.
  These results are used to obtain simplified hardness results for several
graph embedding problems, on more restricted graph classes than previously
known: assuming the Exponential Time Hypothesis, there do not exist algorithms
that run in $2^{o(n/\log n)}$ time for Subgraph Isomorphism on graphs of
pathwidth 1, Induced Subgraph Isomorphism on graphs of pathwidth 1, Graph Minor
on graphs of pathwidth 1, Induced Graph Minor on graphs of pathwidth 1,
Intervalizing 5-Colored Graphs on trees, and finding a tree or path
decomposition with width at most $c$ with a minimum number of bags, for any
fixed $c\geq 16$.
  $2^{\Theta(n/\log n)}$ appears to be the "correct" running time for many
packing and embedding problems on restricted graph classes, and we think String
Crafting and Orthogonal Vector Crafting form a useful framework for
establishing lower bounds of this form.
