- Series
- Graph Theory Seminar
- Time
- Tuesday, November 10, 2020 - 12:30pm for 1 hour (actually 50 minutes)
- Location
- https://us04web.zoom.us/j/77238664391. For password, please email Anton Bernshteyn (bahtoh ~at~ gatech.edu)
- Speaker
- Louis Esperet – Université Grenoble Alpes – louis.esperet@grenoble-inp.fr – https://oc.g-scop.grenoble-inp.fr/esperet/
- Organizer
- Anton Bernshteyn

**Please Note:** Note the unusual time!

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.