pipette
ESEspañol

Tight B-Trees for Adjacency Labeling

Noy Rotbart

Preprint

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.

Main resultThe abstract does not state a limitation.

Appeared: Tuesday, November 10. arXiv. Preprint, not yet peer-reviewed.

Authors' comment: 8 pages, 2 figures