Title: Subgraph-universal planar graphs for trees Show Chinese title

Title: 子图通用平面图对于树

Abstract: We show that there exists an outerplanar graph on $O(n^{c})$ vertices for $c = \log_2(3+\sqrt{10}) \approx 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 $n^{O(\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 $\frac{3}{2}n$, 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 $n^{O(\log(n))}$ vertices containing all $n$-vertex outerplanar graphs as subgraphs. Show Chinese abstract

Abstract: 我们证明存在一个具有$O(n^{c})$个顶点的外平面图，对于$c = \log_2(3+\sqrt{10}) \approx 2.623$，它包含每个具有$n$个顶点的树作为子图。 这扩展了Chung和Graham在1983年的一项结果，他们证明存在(非平面)具有$n$个顶点的图，有$O(n \log n)$条边，包含所有具有$n$个顶点的树作为子图，以及Gol'dberg和Livshits在1968年的一项结果，他们证明存在一个通用树，在$n$个顶点的树上覆盖$n^{O(\log(n))}$个顶点。 此外，我们确定在最坏情况下，平面图要包含三个给定的树作为子图所需的顶点数约为$\frac{3}{2}n$，即使这三个树是毛虫树。 这回答了Alecu等人在2024年提出的一个问题。 最后，我们研究包含所有(外)平面图作为子图的(外)平面图，确定了两种情况下的指数下界。 我们还构造了一个具有$n^{O(\log(n))}$个顶点的平面图，其中包含所有$n$顶点的外平面图作为子图。