Reconfiguration in bounded bandwidth and tree-depth

We show that several reconfiguration problems known to be PSPACE-complete remain so even when limited to graphs of bounded bandwidth (and hence pathwidth and treewidth). The essential step is noticing the similarity to very limited string rewriting systems, whose ability to directly simulate Turing Machines is classically known. On the other hand, we show that a large class of natural reconfiguration problems (coming from graph homomorphisms) becomes tractable on graphs of bounded tree-depth, and prove a dichotomy showing this to be in some sense tight.