Sparse universal graphs for planarity

Abstract We show that for every integer , there exists a graph with vertices and edges such that every ‐vertex planar graph is isomorphic to a subgraph of . The best previous bound on the number of edges was , proved by Babai, Chung, Erdős, Graham, and Spencer in 1982. We then show that for every integer , there is a graph with vertices and edges that contains induced copies of every ‐vertex planar graph. This significantly reduces the number of edges in a recent construction of the authors with Dujmović, Gavoille, and Micek.