# Succinct Permutation Graphs

Sep 2022 (Written: Oct 2020)

Konstantinos Tsakalidis, Sebastian Wild, and Viktor Zamaraev:

Algorithmica (online first)

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.