Efficient Adjacency Labelling for Tree-Like Graph Families

Abstract

This paper delves into the realm of adjacency labelling schemes and their relationship with induced universal graphs, with a focus on a recent construction of nearly optimal adjacency labelling schemes for planar graphs by Dujmović, Esperet, Gavoille, Joret, Micek, and Morin. Adjacency labelling schemes are an essential tool for efficiently representing and querying graph structures, whereas induced universal graphs serve as a powerful combinatorial object providing insights into the relationships between different graph classes.

The goal of this paper is to explain the recent constructions of efficient adjacency labelling schemes for tree-like families, namely graphs of bounded treewidth and planar graphs, which are closely related. In particular, for both of these graph families, there exists a scheme which assigns each vertex of an $n$-vertex planar graph $G$ a $(1+o(1))\log_2 n$-bit label such that the labels of two vertices $u, v \in V(G)$ determines if $uv \in E(G)$. Equivalently, for each positive integer $n$ there exists a graph $U_n$ with $n^{1+o(1)}$ vertices such that every $n$-vertex bounded treewidth graph (or planar graph) is an induced subgraph of $U_n$.

We outline the proof of the theorem for bounded treewidth graph families in chapter 2 after introducing the necessary structural graph theory preliminaries. In chapter 3, a discussion of the latter improvement for planar graph families highlights a combination of techniques from data structures (namely, biased binary search trees and fractional cascading) and structural graph theory (treewidth, strong product, coloring, etc.). Our goal is to highlight the key techniques in the paper and to show, at a high level, how they come together to produce the $(1+o(1))\log_2 n$-bit labels.