Shorter Labeling Schemes for Planar Graphs
Marthe Bonamy, Cyril Gavoille, Michał Pilipczuk · Society for Industrial and Applied Mathematics eBooks · 2019
An adjacency labeling scheme for a given class of graphs is an algorithm that, for every graph $G$ from the class, assigns bit strings (labels) to vertices of $G$ so that for any two vertices $u,v$, whether $u$ and $v$ are adjacent can be determined by a fixed procedure that examines only their labels. It is known that planar graphs with $n$ vertices admit a labeling scheme with labels of bit length $(2+o(1))\log{n}$. In this work we improve this bound by designing a labeling scheme with labels of bit length $(\frac{4}{3}+o(1))\log{n}$. All the labels of the input graph can be computed in polynomial time, while adjacency can be decided from the labels in constant time. In graph-theoretical terms, this implies an explicit construction of a graph on $n^{4/3+o(1)}$ vertices that contains all planar graphs on $n$ vertices as induced subgraphs, improving the previous best upper bound of $n^{2+o(1)}$. Our labeling scheme can be generalized to larger classes of topologically constrained graphs, for instance, to graphs embeddable in any fixed surface or to $k$-planar graphs for any fixed $k$, at the cost of larger second-order terms.