Georgia Institute of Technology College of Sciences

The following are two classical questions in the area of universal graphs.

1. What is the minimum number of vertices in a graph that contains all $n$-vertex planar graphs as induced subgraphs?

2. What is the minimum number of edges in a graph that contains all $n$-vertex planar graphs as subgraphs?

We give nearly optimal constructions for each problem, i.e. with $n^{1+o(1)}$ vertices for Question 1 and $n^{1+o(1)}$ edges for Question 2. The proofs combine a recent structure theorem for planar graphs (of independent interest) with techniques from data structures.

Joint work with V. Dujmovic, C. Gavoille, G. Joret, P. Micek, and P. Morin.