Graph Compression using Graph Grammars

This talk considers a method for compressing graphs into a smaller graph grammar based on the RePair compression scheme. We start by defining the necessary notion of context-free hyperedge replacement grammars using examples. We then extend RePair to graphs using this grammar formalism and discuss how the problem of finding non-overlapping occurrences appears more difficult on graphs than on strings and trees. We also give some intuition on graphs that are difficult to compress with HR grammars, present some experimental results based on a proof-of-concept implementation, and briefly mention how to navigate the represented data without decompression. Short Bio: Fabian Peternek is about to receive his Ph.D. from the University of Edinburgh on the topic of grammar-based compression of graphs. His research includes a generalization of the popular RePair compression scheme to graphs, and also algorithmic results on compressed graph and tree grammars with the aim of achieving polynomial time bounds (with respect to the grammar's size) on queries run on grammars.