Simpler Adjacency Labeling for Planar Graphs with B-Trees
Paweł Gawrychowski, Wojciech Janczewski · Society for Industrial and Applied Mathematics eBooks · 2022
An adjacency labeling scheme consists of an encoder and a decoder. The encoder assigns a binary string, called a label, to each vertex of a given graph G. Then, the decoder should decide, given only the labels assigned to two vertices u and v of the same graph G, whether (u, v) is an edge. While for planar graphs labels consisting of O(log n) bits are not too hard to design, determining the exact constant factor in the upper bound remained a challenging open problem, with the only lower bound being log n. Only very recently, Dujmović et al. [FOCS 2020] were able to bring the upper bound down to log . At the heart of their construction lies a graph product structure theorem that is used to translate the problem into a data-structure question. The latter is then solved by designing a tailored balanced binary search trees that allow for efficient bulk operations. We show how this can be achieved with an arguably simpler approach based on B-Trees, while the other parts of the whole framework remain relatively unchanged. This allows us to obtain a cleaner upper bound of log bits on the length of the labels, and additionally decrease the decoding time to constant.