Tight B-Trees for Adjacency Labeling
In the authors' words
We show that planar graphs admit adjacency labels of size : every vertex gets a label of this many bits, and the adjacency of two vertices is decided from their labels alone, in constant time. This improves the of Dujmovi\'c et al. (J. ACM 2021) and the of Gawrychowski and Janczewski (SOSA 2022). Equivalently, -vertex planar graphs have an induced-universal graph with vertices, down from . The same holds for graphs of bounded genus, apex-minor-free graphs and -planar graphs. For every proper minor-closed class we get , down from the of Dujmovi\'c et al. (2026). Both results come from tight B-trees: nodes are split into parts of nearly equal size, so every node but the topmost stays within a factor of its target size, and a root-to-leaf path loses only bits.
Appeared: Tuesday, November 10. arXiv. Preprint, not yet peer-reviewed.
Authors' comment: 8 pages, 2 figures