Adjacency Labelling for Planar Graphs (and Beyond)

Abstract

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 $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 bounded genus graphs, apex-minor-free graphs, bounded-degree graphs from minor closed families, and $k$-planar graphs.

v4: referees' comments incorporated v3: minor changes v2: significant revision v1: 35 pages; 8 figures

References in corpus (1)

• Clustered 3-Colouring Graphs of Bounded Degree

Cited by in corpus (5)

• Sparse universal graphs for planarity
• Improved product structure for graphs on surfaces
• Product structure of graphs with an excluded minor
• Small But Unwieldy: A Lower Bound on Adjacency Labels for Small Classes
• The grid-minor theorem revisited