Linear-Time Compression of Bounded-Genus Graphs into Information-Theoretically Optimal Number of Bits

Hsueh-I Lu

A $\text{compression scheme}$ $A$ for a class $\mathbb{G}$ of graphs consists of an encoding algorithm ${\text{Encode}}_A$ that computes a binary string ${\text{Code}}_A(G)$ for…