Canonical representations of partial 2- and 3-trees (1992)
Link: https://link.springer.com/article/10.1007/BF01994877
Abstract: We give algorithms constructing canonical representations of partial 2-trees (series parallel graphs) and partial 3-trees. The algorithms can be implemented in log-linear space, or in linear time using quadratic space.
This paper present a very interesting canonization algorithm for partial 2- and 3-trees based on the idea of using reduction rules to continuously reduce the size of the graph until just a single vertex remains. Information about the application of these reduction rules is stored as vertex and edge labels. Although the original form of the algorithm does not support edge labels, vertex labels, digraphs, multi graphs or self loops. The algorithm itself does make use of these, meaning it is possible that extending it to work with a labelled directed graph as input is trivial.
Paper quotes
Most graph representations are not canonical since vertices are arbitrarily numbered. But if we consider all possible vertex permutations, compute the corresponding representations, and select the lexicographically smallest, then we get a canonical representation. The set of vertex permutations yielding the lexicographicaly smallest representation is a coset of the automorphism group for the graph, regarded as a subgroup of the symmetric group on the vertex set.
Previously, the graph isomor- phism problems for the graphs of bounded valence (Luks [18]), genus (Filotti and Mayer [12], Miller [19], [20]), and tree-width (Bodlaender [7]) (none of which is a subfamily of the other) have been shown solvable in polynomial time.
Linear time algorithms for isomorphism of planar graphs (and thus also for partial 2-trees, which are planar) are already known (Fontet [13]; Hopcroft and Wong [t5]; Colbourn and Booth [10]).
While partial k-trees are undirected, simple graphs (without multiple edges or self-loops), in the course of our presentation we will allow both undirected edges and directed arcs (ordered pairs of vertices), as well as parallel edges and arcs.
Our algorithm is based on a construction of (vertex and edge) labels that record the sequence of reduction of the original graph G leading to a set of labeled isolated vertices. From these, we construct the final label that is a canonical representation of G and, as such, would also allow a unique (and efficient) reconstruction of G.