Treewidth Bounds for Planar Graphs Using Three-Sided Brambles

arXiv1706.08581MaRDI QIDQ6288323FDOQ6288323

Authors: Karen L. Collins, Brett C. Smith 

Publication date: 26 June 2017

Abstract: 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)/4leqKBleqBN(G)leq4KBleq4lambda(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)geqs(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.

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph minors (05C83)

This page was built for publication: Treewidth Bounds for Planar Graphs Using Three-Sided Brambles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6288323)