Optimal Induced Universal Graphs and Adjacency Labeling for Trees
Stephen Alstrup, Søren Dahlgaard, Mathias Bæk Tejs Knudsen · Journal of the ACM · 2017
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 2 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.