CS Paper Radar

Tight B-Trees for Adjacency Labeling

Noy Rotbart

cs.DS cs.DM ·submitted 2026-11-08 15:12 UTC · v1

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.

Comment
8 pages, 2 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Adjacency Labeling Schemes of Size $\log n+O(\log\log^* n)$ for Graphs of Bounded Treewidth

cs.DS cs.DM ·2026-11-02 ·Noy Rotbart
similarity 0.80
Abstract · 23 pages, 9 figures

Gavoille and Labourel (ESA 2007) gave an adjacency labeling scheme of size $\log n+O(k\log\log n)$ for graphs of treewidth at most $k$, and asked whether $\log n+O(k)$ bits suffice. We give a labeling scheme of size $\log n+O(\log\log^* n)$ for every fixed $k$, the first improvement of the second-order term for any $k\ge 2$. Equivalently, there is an induced-universal graph with $n(\log^* n)^{O_k(1)}$ vertices for this family. We work with laminar families of intervals, in which a vertex finds each earlier neighbor as the owner of an interval of a given nesting depth around it. As long as every subtree occupies consecutive positions, the nesting depth must be logarithmic, and $\log\log n$ bits per neighbor follow. We give up contiguity. Heavy subtrees are moved out, which brings the depth down to $O(\log^* n)$; the intervals broken by the moves are repaired with $2^{O(k^3)}$ additional intervals per vertex; and the bits needed to find these intervals are paid for by the moved subtrees.

0.30

Small classes have linear neighbourhood complexity

cs.DM math.CO ·2026-11-11 ·John Sylvester, Viktor Zamaraev, Maksim Zhukovskii
theory similarity 0.73
Abstract · 31 pages, 6 figures

A hereditary graph class is small if it contains at most $n!c^n$ labelled graphs on $n$ vertices for some constant $c$. Small classes include proper minor-closed classes and classes of bounded twin-width. We prove that every small class has linear neighbourhood complexity, that is, in every graph in the class, vertex neighbourhoods intersect any $k$-vertex set in only $O(k)$ distinct ways. This resolves a conjecture of Bonnet, Duron, and the first two authors (ITCS 2025) and makes the algorithmic, structural, and representation consequences of linear neighbourhood complexity available for every small class. In particular, every small class admits an adjacency labelling scheme with $O(\log^2 n)$-bit labels, improving the previous $O(\log^3 n)$ bound.

0.20

Asymptotic dimension of graphs excluding an induced or fat minor

cs.DM math.CO ·2026-10-15 ·Robert Hickingbotham, Freddie Illingworth, Piotr Micek, Bartosz Walczak
theory similarity 0.71
Abstract

Asymptotic dimension is a large-scale invariant of metric spaces that was introduced by Gromov (1993). A major open problem in coarse graph theory asks whether, for every fixed graph $H$, the class of graphs excluding $H$ as a fat minor has bounded asymptotic dimension. A weaker conjecture asserts the same conclusion for graphs excluding $H$ as an induced minor. We substantially expand the range of graphs $H$ for which these conjectures are known to hold. Specifically, we prove bounded asymptotic dimension for the following classes of graphs: graphs excluding a fixed planar graph as a fat minor; and graphs excluding a fixed string graph as an induced minor. All of our results also hold for the stronger notion of Assouad--Nagata dimension, a refinement of asymptotic dimension. These results have a number of applications, two of which we mention here. First they imply that an induced minor-closed class is $χ$-bounded if and only if it does not contain some Burling graph. Second they imply that, in graph classes excluding a fixed planar graph as an induced minor, treewidth is polynomial in maximum degree.

0.24

Logarithmic basis number of graphs and regular matroids

cs.DM math.CO ·2026-09-02 ·Kolja Knauer
theory similarity 0.68
Abstract · 13 pages

The basis number $bn(G)$ of a graph $G$ is the minimum edge-congestion of a basis of its cycle space. We prove that every finite $n$-vertex multigraph satisfies $bn(G)=O(\log n)$, resolving, for simple graphs, a question of Bazargani, Biedl, Bose, Maheshwari and Miraftab, subsequently stated as a conjecture by Miraftab, Morin and Yuditsky. The argument also yields the cycle-rank refinement $bn(G)=O(\log β(G))$, where $β(G)$ is the dimension of the cycle space, and a reduction of Lehner and Miraftab, based on a theorem of Richter and Shank, then gives $bn(G)=O(\log g)$ for graphs of Euler genus $g$. For regular matroids we prove the ground-set bound $bn(M)=O(\log m)$, where $m=|E(M)|$, and logarithmic bounds in both the rank $r(M)$ and the cycle-space dimension $d$. All these orders are best possible.

0.51

Treewidth 3 in the Product Structure Theorem for Bounded Degree Graphs in Minor-Closed Classes

cs.DM math.CO ·2026-11-18 ·Vida Dujmović, Robert Hickingbotham, Pat Morin, David R. Wood
theory similarity 0.68
Abstract · 28 pages, 4 figures, written by humans

We show that, for all positive integers $t$ and $Δ$, there exists an integer $c$ such that, for every $K_t$-minor-free graph $G$ with maximum degree at most $Δ$, there exists a graph $H$ of treewidth at most $3$ and a path $P$ such that $G$ is isomorphic to a subgraph of the strong product $H\boxtimes P\boxtimes K_c$. This improves on a previous result of Dujumović, Esperet, Micek, Walczak, and Wood (2022) by bounding the treewidth of $H$ independently of $t$ and $Δ$. As an immediate consequence we obtain a bound of $O(r^4)$ on the $r$-weak colouring number of bounded-degree graphs from any proper minor-closed graph class.

0.21

You Can Have It All: Small sparse induced-universal graphs for minor-closed classes

cs.DM math.CO ·2026-11-10 ·Vida Dujmović, Cyril Gavoille, Gwenaël Joret, Piotr Micek, Pat Morin +1 more
similarity 0.68
Abstract · Extends the results in arXiv:2605.06616 to produce induced-universal graphs with $n^{1+o(1)}$ edges and vertices

We show that, for every fixed proper minor-closed graph class $\mathcal{G}$ and every positive integer $n$, there exists a graph $U_n$ with $n^{1+o(1)}$ vertices and edges such that every $n$-vertex graph in $\mathcal{G}$ is isomorphic to an induced subgraph of $U_n$. This result generalizes and unifies the results of Dujmović et al. (J. ACM 2021) on induced-universal graphs and the results of Esperet, Joret, and Morin (J. London Math. Soc. 2023) on sparse induced-universal graphs from planar graphs to all proper minor-closed graph classes. It simultaneously improves the previous bounds for the number of vertices in induced-universal graphs (previously $O(n^2)$ obtained as a corollary of a result of DeVos et al. (J. Comb. Theory, Ser. {B} 2004) and a result of Gavoille and Labourel (ESA 2007)) and the number of edges in subgraph-universal graphs (previously $O(n^{3/2})$ by Babai et al. (Theory and Practice of Combinatorics 1982)).

0.20

Vertex Deletion on $H$-Induced-Minor-Free Graphs: Subexponential FPT Algorithms and Approximation Schemes

cs.DS cs.DM ·2026-11-06 ·Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Jie Xue, Meirav Zehavi
similarity 0.68
Abstract

We study vertex-deletion problems on string graphs and, more generally, on graphs excluding a fixed graph as an induced minor. For every fixed graph $H$, fixed nonnegative integer $t$, and fixed monadic second-order formula $φ$, we consider the problem of finding a minimum-cardinality set $S$ such that $G-S$ has treewidth at most $t$ and satisfies $φ$. This captures classic problems such as Vertex Cover, Feedback Vertex Set, and deletion to graphs of any fixed bounded treewidth. We give an algorithm with running time $2^{k^{2/3} \log^{O(1)} k}n^{O(1)}$ on $H$-induced-minor-free graphs, where $k$ is the optimum deletion-set size. This resolves in the affirmative the open problem highlighted by Bonnet and Rzążewski [Algorithmica 2019] and Berthe, Bougeret, Gonçalves, and Raymond [ICALP 2025] regarding the existence of a subexponential parameterized algorithm for Feedback Vertex Set on string graphs. Our algorithm significantly improves over existing parameterized algorithms for more restricted classes of problems on more restricted classes of graphs. When the property defined by $φ$ is hereditary, we also obtain a quasi-polynomial time approximation scheme, namely an algorithm that produces a $(1+\varepsilon)$-approximate solution in quasi-polynomial time. Both the sub-exponential algorithm and the quasi-polynomial time approximation scheme build on the same new structural and algorithmic insights.

0.20

On (Pathwidth, Clique)-boundedness

cs.DM math.CO ·2026-11-17 ·Amir Nikabadi
theory similarity 0.66
Abstract

We prove that every $(\pw,ω)$-bounded class of graphs has bounded tree-independence number, answering a question of Bešter Štorgel, Dallard, Lozin, Milanič, and Zamaraev. We deduce this from a bound on the tree-independence number of graphs with neither $\B_ρ$ nor $K_{σ,σ}$ as an induced minor, where $\B_ρ$ is the complete binary tree of height $ρ$ and the bound depends only on $ρ$ and $σ$. We then obtain an asymptotically sharp bound on the path-independence number of $n$-vertex graphs in any $(\pw,ω)$-bounded class. The lower-bound examples also give counterexamples to a conjecture of Hickingbotham and Joret. We further prove that, for every forest $F$ and every $\ell\in\N$, there is a constant $k=k(F,\ell)\in\N$ such that every graph $G$ with no induced theta or $\ell$-long prism and no induced subgraph isomorphic to $F$ satisfies tree-independence number at most $k$. This proves a strengthened form of a conjecture of Chudnovsky, Hajebi, and Trotignon. Finally, for every integer $s\ge2$, we characterize the forests $F$ for which excluding $F$ as an induced minor and $K_{s,s}$ as an induced subgraph bounds tree-independence number. This extends the characterization of Bonnet, Duhamel, and Hickingbotham, who considered bounded pathwidth with $K_{s,s}$ excluded as a subgraph.

0.09