On space efficiency of algorithms working on structural decompositions of graphs

Motivated by failed attempts at making dynamic algorithms on tree-width use less space (without using more time), we look at this from a complexity-theoretic point of view. I will mention relations to Savitch's theorem and then show how the problem of solving, say, 3-Coloring on graphs of treewidth, pathwidth, tree-depth at most s(n) is complete for classes of nondet. poly-time Turing machines with different stack access to ~s(n) memory. This gives a nice hierarchy with some corollaries.