  We show that there exists a graph $G$ with $O(n)$ nodes, where any forest of
$n$ nodes is a node-induced subgraph of $G$. Furthermore, for constant
arboricity $k$, the result implies the existence of a graph with $O(n^k)$ nodes
that contains all $n$-node graphs as node-induced subgraphs, matching a
$\Omega(n^k)$ lower bound. The lower bound and previously best upper bounds
were presented in Alstrup and Rauhe (FOCS'02). Our upper bounds are obtained
through a $\log_2 n +O(1)$ labeling scheme for adjacency queries in forests.
  We hereby solve an open problem being raised repeatedly over decades, e.g. in
Kannan, Naor, Rudich (STOC 1988), Chung (J. of Graph Theory 1990), Fraigniaud
and Korman (SODA 2010).
