A Logspace Algorithm for Partial 2-Tree Canonization (2008)

Link: https://link.springer.com/chapter/10.1007/978-3-540-79709-8_8

Abstract: We show that partial 2-tree canonization, and hence isomorphism testing for partial 2-trees, is in deterministic logspace. Our algorithm involves two steps: (a) We exploit the “tree of cycles” property of biconnected partial 2-trees to canonize them in logspace. (b) We analyze Lindell’s tree canonization algorithm and show that canonizing general partial 2-trees is also in logspace, using the algorithm to canonize biconnected partial 2-trees.

The suggested approach does not support directed graphs and edge labels (though vertex labels appear supported), quoting from the paper “By graphs we mean finite simple graphs”. A second variant does support a coloured graph input though (vertex colours).

Some useful properties from the paper:

  1. Partial 2-trees are planar graphs.
  2. An automorphism of a graph is an isomorphism from the graph to itself.