Sparse universal graphs for planarity
We show that for every integer n⩾ 1 n\geqslant1, there exists a graph G n G_n with (1+ o (1))
n (1+o(1))n vertices and n 1+ o (1) n^1+o(1) edges such that every nn‐vertex planar graph is
isomorphic to a subgraph of G n G_n. The best previous bound on the number of edges was
O (n 3/2) O(n^3/2), proved by Babai, Chung, Erdős, Graham, and Spencer in 1982. We then
show that for every integer n⩾ 1 n\geqslant1, there is a graph U n U_n with n 1+ o (1)
n^1+o(1) vertices and edges that contains induced copies of every nn‐vertex planar graph …
n (1+o(1))n vertices and n 1+ o (1) n^1+o(1) edges such that every nn‐vertex planar graph is
isomorphic to a subgraph of G n G_n. The best previous bound on the number of edges was
O (n 3/2) O(n^3/2), proved by Babai, Chung, Erdős, Graham, and Spencer in 1982. We then
show that for every integer n⩾ 1 n\geqslant1, there is a graph U n U_n with n 1+ o (1)
n^1+o(1) vertices and edges that contains induced copies of every nn‐vertex planar graph …
Abstract
We show that for every integer n⩾1$n\geqslant 1$, there exists a graph Gn$G_n$ with (1+o(1))n$(1+o(1))n$ vertices and n1+o(1)$n^{1 + o(1)}$ edges such that every n$n$‐vertex planar graph is isomorphic to a subgraph of Gn$G_n$. The best previous bound on the number of edges was O(n3/2)$O(n^{3/2})$, proved by Babai, Chung, Erdős, Graham, and Spencer in 1982. We then show that for every integer n⩾1$n\geqslant 1$, there is a graph Un$U_n$ with n1+o(1)$n^{1 + o(1)}$ vertices and edges that contains induced copies of every n$n$‐vertex planar graph. This significantly reduces the number of edges in a recent construction of the authors with Dujmović, Gavoille, and Micek.
Wiley Online Library
以上显示的是最相近的搜索结果。 查看全部搜索结果