Treewidth Bounds for Planar Graphs Using Three-Sided Brambles

Karen L. Collins, Brett C. Smith

Published 2017-06-26Version 1

Square grids play a pivotal role in Robertson and Seymour's work on graph minors as planar obstructions to small treewidth. We introduce a three-sided bramble in a plane graph called a net, which generalizes the standard bramble of crosses in a square grid. We then characterize any minimal cover of a net as a tree drawn in the plane. We use nets in an $O(n^3)$ time algorithm that computes both upper and lower bounds on the bramble number (hence treewidth) of any planar graph. Let $G$ be a planar graph, $BN(G)$ be its bramble number and $\lambda(G)$ be the largest order of any net in a subgraph of $G$. Our algorithm outputs a constant, $KB$, so that $\lambda(G)/4 \leq KB \leq BN(G)\leq 4KB \leq 4\lambda(G)$. Let $s(G)$ be the size of a side of the largest square grid minor of $G$. Smith (2015) has shown that $\lambda(G) \geq s(G)$. Our upper bound improves that of Grigoriev (2011) when $\lambda(G)\leq (5/4)s(G)$. We correct a lower bound of Bodlaender, Grigoriev and Koster (2008) to $s(G)/5$ (instead of $s(G)/4$) and thus the lower bound of $\lambda(G)/4$ on our approximation is an improvement.