Results

This site presents the notes for a now concluded project on CPQ query graph canonization. The final report titled CPQ Keys: a survey of graph canonization algorithms is available for reading and the repository with all the code is available at RoanH/CPQKeys.

Notes

Literature

Extended notes for specific papers:

Current State

The current state of graph canonization for edge labelled directed graphs of treewidth 2 is not very rich. There are a lot of algorithms for undirected graphs without edge labels. Some of these algorithms even achieve very good runtimes with some extra assumptions (e.g. planar graph, DAG, trees). However, work on extending these existing techniques to edge labelled or directed graphs is fairly limited. Some algorithms that support directed graphs do exist, such as nauty, bliss and conauto. For edge labels Scott claims that it is the only algorithm that supports them (this claim is both in the original 2019 paper and in the 2020 follow up paper). Presently, this still seems to be the case as the original Scott paper has only been cited twice according to Google scholar. So far I have not found any algorithms that natively support both edge labels and directed graphs.