Shorter Labeling Schemes for Planar Graphs
share
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))n. In this work we improve this bound by designing a labeling scheme with labels of bit length (4/3+o(1))n. 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 scheme generalizes to graphs of bounded Euler genus with the same label length up to a second-order term. All the labels of the input graph can be computed in polynomial time, while adjacency can be decided from the labels in constant time.
READ FULL TEXT