Planar graphs get smaller adjacency labels for faster connections
Tight B-Trees for Adjacency Labeling
Data Structures and AlgorithmsDiscrete Mathematics
Summary
The paper improves how we assign short codes (labels) to points in certain types of networks called planar graphs, so that by looking only at these codes, we can instantly tell if two points are connected. The authors made these codes even shorter than before, saving space and making the check more efficient. This also helps represent these networks inside larger, universal maps that are more compact. Their technique applies not just to planar graphs, but also to other related kinds of networks, making it broadly useful.
What this means in practice
- •For network protocol developers: Create communication systems that quickly decide if two devices are directly connected using small, constant-time labels.
- •For database system architects: Design more space-efficient data structures for planar and similar graphs enabling faster adjacency queries without large lookups.
A theory result. No direct application yet.
Authors
Noy Rotbart
Abstract
We show that planar graphs admit adjacency labels of size $\log n+O(\log\log n)$: 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 $\log n+O(\sqrt{\log n\log\log n})$ of Dujmović et al. (J. ACM 2021) and the $\log n+O(\sqrt{\log n})$ of Gawrychowski and Janczewski (SOSA 2022). Equivalently, $n$-vertex planar graphs have an induced-universal graph with $n(\log n)^{O(1)}$ vertices, down from $n2^{O(\sqrt{\log n})}$. The same holds for graphs of bounded genus, apex-minor-free graphs and $k$-planar graphs. For every proper minor-closed class we get $\log n+O(\sqrt{\log n\log\log n})$, down from the $\log n+O((\log n)^{3/4})$ of Dujmović 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 $1\pm O(1/\log n)$ of its target size, and a root-to-leaf path loses only $O(\log\log n)$ bits.