@Article{ADKK12ktree-canonization,
  author =       {V. Arvind and Bireswar Das and Johannes Köbler and Sebastian Kuhnert},
  title =        {The isomorphism problem for $k$-trees is complete for logspace},
  journal =      {Information and Computation},
  year =         2012,
  volume =       217,
  month =        8,
  pages =        {1-11},
  issn =         {0890-5401},
  doi =          {10.1016/j.ic.2012.04.002},
}

The isomorphism problem for k-trees is complete for logspace.
With V. Arvind, Bireswar Das, Johannes Köbler.
Information and Computation 217:1–11 (Aug. 2012)

Abstract. We show that, for k constant, k-tree isomorphism can be decided in logarithmic space by giving an O(nlogn) space 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 a variant of our canonical labeling algorithm runs in time O((k+1)!logn), where n is the number of vertices, yielding the fastest known FPT algorithm for k-tree isomorphism.

@InProceedings{KK09ktree-canonization,
  author =       {Johannes Köbler and Sebastian Kuhnert},
  title =        {The isomorphism problem for $k$-trees is complete for logspace},
  booktitle =    {Mathematical Foundations of Computer Science 2009. 
                  34th International Symposium (MFCS)},
  year =         2009,
  series =       {LNCS},
  number =       5734,
  publisher =    {Springer},
  address =      {Berlin},
  isbn =         {978-3-642-03815-0},
  doi =          {10.1007/978-3-642-03816-7_46},
  pages =        {537-548},
}

Conference version:
The isomorphism problem for k-Trees is complete for logspace
With Johannes Köbler.
Mathematical Foundations of Computer Science (Proceedings of 34th MFCS). Springer, 2009. Pp. 537–548.