pipette
ENEnglish

Tight B-Trees for Adjacency Labeling

Noy Rotbart

Preprint

En palabras de los autores

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.

Resultado principalEl resumen no menciona limitaciones.

Apareció: martes, 10 de noviembre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: 8 pages, 2 figures