Succinct Permutation Graphs
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.
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.