Adjacency labelling for proper minor-closed graph classes
2026-05-07 • Discrete Mathematics
Discrete Mathematics
AI summaryⓘ
The authors found a way to label the connections between nodes in certain types of graphs (called proper minor-closed classes) using about log-base-2 of the number of nodes bits, which is very efficient. They also showed that for these graph classes, you can build a big graph containing all smaller graphs in the class as parts within it. Both of these results are nearly the best possible. Essentially, this helps in storing and representing these graphs compactly.
graph theoryminor-closed classesadjacency labeling schemeinduced subgraphgraph isomorphismgraph embeddingbit complexityvertex labeling
Authors
Vida Dujmović, Gwenaël Joret, Cyril Gavoille, Piotr Micek, Pat Morin, David R. Wood
Abstract
We show that every proper minor-closed class of graphs admits a $(1+o(1))\log_2 n$-bit adjacency labelling scheme. Equivalently, for every proper minor-closed class $\mathcal{G}$ and every positive integer $n$ there exists an $n^{1+o(1)}$-vertex graph $U$ such that every $n$-vertex graph in $\mathcal{G}$ is isomorphic to an induced subgraph of $U$. Both results are optimal up to the lower order term.