Optimal induced universal graphs and adjacency labeling for trees

In this article, we show that there exists a graph G with O(n) nodes such that any forest of n nodes is an 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 of arboricity k as node-induced subgraphs, matching a Ω(n^k) lower bound of Alstrup and Rauhe. Our upper bounds are obtained through a log₂ n + O(1) labeling scheme for adjacency queries in forests. We hereby solve an open problem being raised repeatedly over decades by authors such as Kannan et al., Chung, and Fraigniaud and Korman.