Planar graphs with no grid minor have smaller treewidth bounds
An improved bound on the treewidth of planar graphs excluding a grid minor
Discrete Mathematics
Summary
The paper finds a better limit on how complex certain flat networks can be, specifically those that don't contain a big grid shape inside them. The authors improve a previous estimate on a measure called treewidth, which relates to how tree-like a network is. They also show a related technical result about breaking down graphs drawn on a plane, which could be useful elsewhere. This helps understand the structure of planar graphs better.
What this means in practice
- •For graph algorithm developers: Design algorithms optimized for planar graphs by using improved bounds on treewidth to better manage complexity in the absence of large grid minors.
- •For network topology planners: Better understand constraints on planar network designs to simplify routing and fault tolerance planning when large grid-like patterns are avoided.
A theory result. No direct application yet.
Authors
Wouter Cames van Batenburg, Quentin Claus, Gwenaël Joret, Robin Petit, Jean-Florent Raymond, Eileen Robinson
Abstract
We show that every planar graph with no $t \times t$ grid minor has treewidth at most $4t +4$. This improves on the previously best known bound of $\frac{9}{2}t - \frac{11}{2}$, due to Gu and Tamaki (2012), and is within a factor $2$ of optimal. A key step in the proof is showing the following result, which might be of independent interest: Every $2$-connected plane graph $G$ with radius $d$ and faces of size at most $k$ has a tree-decomposition of width at most $\max\{3d+ k+5, 2d+2k+1\}$ such that the vertex set of every face of $G$ is contained in some bag.