Adjacency Labelling for Planar Graphs (and Beyond)

Exposé de Cyril Gavoille dans le cadre du séminaire Algorithmique Distribuée du LaBRI (U. Bordeaux).

Résumé : 
We show that there exists an adjacency labelling scheme for planar graphs 
where each vertex of an $n$-vertex planar graph $G$ is assigned a 
$(1+o(1))\log_2 n$-bit label and the labels of two vertices $u$ and $v$ are 
sufficient to determine if $uv$ is an edge of $G$. This is optimal up to 
the lower order term and is the first such asymptotically optimal result. 
An alternative, but equivalent, interpretation of this result is that, for 
every positive integer $n$, there exists a graph $U_n$ with $n^{1+o(1)}$ 
vertices such that every $n$-vertex planar graph is an induced subgraph of 
$U_n$. These results generalize to a number of other graph classes, 
including bounded genus graphs, apex-minor-free graphs, bounded-degree 
graphs from minor closed families, and $k$-planar graphs. This work will 
appear at FOCS'20 and is joint with Vida Dujmović, Louis Esperet, Gwenaël 
Joret and Pat Morin.