Basis Number of Graphs Excluding Minors
By: Colin Geniet, Ugo Giocanti
Potential Business Impact:
Finds simpler ways to draw complex maps.
The basis number of a graph $G$ is the minimum $k$ such that the cycle space of $G$ is generated by a family of cycles using each edge at most $k$ times. A classical result of Mac Lane states that planar graphs are exactly graphs with basis number at most 2, and more generally, graphs embedded on a fixed surface are known to have bounded basis number. Generalising this, we prove that graphs excluding a fixed minor $H$ have bounded basis number. Our proof uses the Graph Minor Structure Theorem, which requires us to understand how basis number behaves in tree-decompositions. In particular, we prove that graphs of treewidth $k$ have basis number bounded by some function of $k$. We handle tree-decompositions using the proof framework developed by Bojańczyk and Pilipczuk in their proof of Courcelle's conjecture. Combining our approach with independent results of Miraftab, Morin and Yuditsky (2025) on basis number and path-decompositions, one can moreover improve our upper bound to a polynomial one: there exists an absolute constant $c>0$ such that every $H$-minor free graph has basis number $O(|H|^c)$.
Similar Papers
Bounds on treewidth via excluding disjoint unions of cycles
Combinatorics
Finds patterns in networks faster.
Excluding a Forest Induced Minor
Combinatorics
Finds patterns in networks, even when parts are missing.
Unavoidable butterfly minors in digraphs of large cycle rank
Combinatorics
Finds patterns in connected paths to understand complex networks.