Ultra-succinct graphs  ·  Mode 1: the data structure

Concatenate every out-neighbourhood into one string A, mark where each neighbourhood begins in a bitvector S, and store A in an entropy-compressed wavelet tree. That is the whole representation — and every navigational operation becomes a constant number of rank / select calls. A costs m·H₀(A) bits, and H₀(A) is exactly the graph's zeroth-order in-degree entropy. Step 2 attacks that term by extracting a tree. Nothing is renamed here: vertices keep the input's own names 0 … n−1, and only array positions are 1-based, as in the paper. The relabelling arrives in Step 2, where the extracted tree induces it.

Pick the edges of a tree T — click them in the graph, or let the greedy MST approximation of the paper choose — then extract. T leaves the adjacency string behind as a red dashed shadow, its level-order traversal renames every vertex 1 … n, and the tree itself is stored as LOUDS plus one direction bit per edge. Only the residual graph G − T is left in A′. Click a vertex to root its component there; hover a tree node to find it in the graph.

Twins are vertices with identical neighbourhoods; in an unlabelled graph nothing tells them apart, so it is enough to remember how many copies each vertex has. Contract every twin class to one representative, record the class sizes in unary in a bitvector B, and store the twin-free graph G₀ with TREX exactly as in Step 2. Adjacency still costs what it did; degree and random access into a neighbourhood are what you give up.

Every refinement of Mode 1 costs something and saves something. Here each one is priced on the same graph, with the bits information theory forces kept apart from the o(·) redundancy that succinct rank/select structures add — on a graph small enough to draw, the redundancy would swamp everything, which is why it sits in its own column. The last panel asks the other question: how much of the possible saving does tree extraction actually get?