Adjacency Labelling for Planar Graphs (and Beyond)

Vida Dujmović, Louis Esperet, Gwenaël Joret +3

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 lab…