define 1 A succinct encoding of F: encode : F → {0, 1}∗, decode : {0, 1}∗ → F lossless: decode(encode(G)) = G for G ∈ F. succinct: G ∈ Fn |encode(G)| = log 2 (|Fn|)·(1+o(1)) efficient: encode, decode efficiently computable (say polytime) 2 A succinct data structure for F (for adjacency): succinct encoding plus adjacency-list queries adjacent(v, u): 1 if vu ∈ E(G) else 0 nextNeigbor(v, u): successor of u in v’s adj list computable efficiently on word-RAM say o(log(|Fn|)) time; often O(1) (potentially more queries) 3 A succinct labeling scheme for F (for adjacency): : V(G) → {0, 1}∗, labelAdj : {0, 1}∗ × {0, 1}∗ → {0, 1} labelAdj( (v), (u)) = adjacent(v, u) for v, u ∈ V(G). succinct: G ∈ Fn | (v)| 1 n log 2 (|Fn|)(1 + o(1)) weaker version: compact: | (v)| = O( 1 n log 2 (|Fn|)) (labels and decoder can differ for each G ∈ F, but heredity puts limits on that) Sebastian Wild Putting your graphs on a diet 2022-10-27 3 / 24