Succinct Permutation Graphs

Sep 2022 (Written: Oct 2020)

Konstantinos Tsakalidis, Sebastian Wild, and Viktor Zamaraev:

Algorithmica 85, 2, pp 509–543 (2023)

We describe succinct data structures for permutation graphs and related classes that use minimal space to store such a graph while allowing efficient access and algorithms on the graph.

More specifically, we store a permutation graph using $n\lg n + o(n \log n)$ bits of space and can simulate an adjacency-list based representation, which would naively require $\Theta(n+m)$ words of space.

A permutation graph in different representations: intersections of chords and grid points — A permutation graph (bottom right) in two representations: as permutation diagram (intersections of chords) and as point grid (bottom right).

Moreover, we support further operations not directly possible on adjacency lists; in particular, we support computing the shortest-path distance between two nodes in constant time, using the succinct data structure for unit interval graphs from our interval graph paper as a key component.