Subgraph-universal planar graphs for trees

We show that there exists an outerplanar graph on O(nᶜ) vertices for c = log₂(3+√10) ≈ 2.623 that contains every tree on n vertices as a subgraph. This extends a result of Chung and Graham from 1983 who showed that there exist (non-planar) n-vertex graphs with O(n log n) edges that contain all trees on n vertices as subgraphs and a result from Gol'dberg and Livshits from 1968 who showed that there exists a universal tree for n-vertex trees on nO(log(n)) vertices. Furthermore, we determine the number of vertices needed in the worst case for a planar graph to contain three given trees as subgraph to be on the order of 3/2n, even if the three trees are caterpillars. This answers a question recently posed by Alecu et al. in 2024. Lastly, we investigate (outer)planar graphs containing all (outer)planar graphs as subgraph, determining exponential lower bounds in both cases. We also construct a planar graph on nO(log(n)) vertices containing all n-vertex outerplanar graphs as subgraphs.