Universal Graphs for Bounded-Degree Trees and Planar Graphs
Sandeep N. Bhatt, Fan Chung, Frank Thomson Leighton, Arnold L. Rosenberg · SIAM Journal on Discrete Mathematics · 1989
How small can a graph be that contains as subgraphs all trees on n vertices with maximum degree d? In this paper, this question is answered by constructing such universal graphs that have n vertices and bounded degree (depending only on d). Universal graphs with n vertices and $O(n\log n)$ edges are also constructed that contain all bounded-degree planar graphs on n vertices as subgraphs. In general, it is shown that the minimum universal graph containing all bounded-degree graphs on n vertices with separators of size $n^\alpha $ has $O(n)$ edges if $\alpha \frac{1}{2}$.