  A $\textit{compression scheme}$ $A$ for a class $\mathbb{G}$ of graphs
consists of an encoding algorithm $\textit{Encode}_A$ that computes a binary
string $\textit{Code}_A(G)$ for any given graph $G$ in $\mathbb{G}$ and a
decoding algorithm $\textit{Decode}_A$ that recovers $G$ from
$\textit{Code}_A(G)$. A compression scheme $A$ for $\mathbb{G}$ is
$\textit{optimal}$ if both $\textit{Encode}_A$ and $\textit{Decode}_A$ run in
linear time and the number of bits of $\textit{Code}_A(G)$ for any $n$-node
graph $G$ in $\mathbb{G}$ is information-theoretically optimal to within
lower-order terms. Trees and plane triangulations were the only known
nontrivial graph classes that admit optimal compression schemes. Based upon
Goodrich's separator decomposition for planar graphs and Djidjev and
Venkatesan's planarizers for bounded-genus graphs, we give an optimal
compression scheme for any hereditary (i.e., closed under taking subgraphs)
class $\mathbb{G}$ under the premise that any $n$-node graph of $\mathbb{G}$ to
be encoded comes with a genus-$o(\frac{n}{\log^2 n})$ embedding. By Mohar's
linear-time algorithm that embeds a bounded-genus graph on a genus-$O(1)$
surface, our result implies that any hereditary class of genus-$O(1)$ graphs
admits an optimal compression scheme. For instance, our result yields the
first-known optimal compression schemes for planar graphs, plane graphs, graphs
embedded on genus-$1$ surfaces, graphs with genus $2$ or less, $3$-colorable
directed plane graphs, $4$-outerplanar graphs, and forests with degree at most
$5$. For non-hereditary graph classes, we also give a methodology for obtaining
optimal compression schemes. From this methodology, we give the first known
optimal compression schemes for triangulations of genus-$O(1)$ surfaces and
floorplans.
