Compact representation for matrices of bounded twin-width

Michał Pilipczuk, Marek Sokołowski, Anna Zych-Pawlewicz

For every fixed $d\in \mathbb{N}$, we design a data structure that represents a binary $n\times n$ matrix that is $d$-twin-ordered. The data structure occupies $O_d(n)$ bits, whi…