Papers for

network topology planners

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Planar graphs with no grid minor have smaller treewidth bounds

An improved bound on the treewidth of planar graphs excluding a grid minor

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.

Mon 14 SeptDiscrete Mathematics
The gist
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.
Open → 2609.15596v1