We show that, for $k$ constant, $k$-tree isomorphism can be decided in logarithmic space by giving a logspace canonical labeling algorithm. The algorithm computes a unique tree decomposition, uses colors to fully encode the structure of the original graph in the decomposition tree and invokes Lindell's tree canonization algorithm. As a consequence, the isomorphism, the automorphism, as well as the canonization problem for $k$-trees are all complete for deterministic logspace. Completeness for logspace holds even for simple structural properties of $k$-trees. We also show that isomorphism of all $k$-trees, $k\ge 1$, is fixed parameter tractable with respect to $k$ by giving an algorithm running in time $O((k+2)!\cdot m)$, where $m$ is the number of edges in the input graph.

This revision includes the relevant parts of the intermediate StUL result of Arvind, Das, and Koebler, introducing Arvind and Das as co-authors. Also, the hardness results are improved and a section is added that describes an FPT algorithm for k-tree canonization with k as parameter.

We show that k-tree isomorphism can be decided in logarithmic
space by giving a logspace canonical labeling algorithm. This improves
over the previous StUL upper bound and matches the lower bound. As a
consequence, the isomorphism, the automorphism, as well as the
canonization problem for k-trees are all complete for deterministic
logspace. We also show that even simple structural properties of k-trees
are complete for logspace.