Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 57 min ago
PreprintarXiv licencearXiv

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

  • Wouter Cames van Batenburg
  • Quentin Claus
  • Gwenaël Joret
  • Robin Petit
  • Jean-Florent Raymond
  • Eileen Robinson
Open at sourcePDFDOICite

Abstract

We show that every planar graph with no t × t grid minor has treewidth at most 4t +4. This improves on the previously best known bound of 9/2t − 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.

Related

  1. Bounds on Treewidth via Excluding Disjoint Unions of Cycles
    Meike Hatzel, Chun-Hung Liu, Bruce Reed +1
    The Electronic Journal of CombinatoricsPeer-reviewedCC BY 4.0Full textCombinatorics & discrete mathematicsCrossref
  2. An improved bound on the support diameter of nonnegative planar Euler vorticity
    Daomin Cao, Junhong Fan, Guodong Wang
    arXivPreprintarXiv licenceFull textAnalysis & PDEsarXiv
  3. Induced packing treewidth II. Excluding a clique or a biclique
    Amir Nikabadi, Paweł Rzążewski
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. A sharp asymptotic bound for odd cycles in planar graphs
    Zhen Liu, Chuanshu Wu
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. An improved bound for the intersection of two longest cycles in k-connected graphs
    Juan Gutiérrez
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{batenburg2026improved,
  title = {{An improved bound on the treewidth of planar graphs excluding a grid minor}},
  author = {Wouter Cames van Batenburg and Quentin Claus and Gwenaël Joret and Robin Petit and Jean-Florent Raymond and Eileen Robinson},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.15596},
  eprint = {2609.15596},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.15596},
}
RIS
TY  - UNPB
TI  - An improved bound on the treewidth of planar graphs excluding a grid minor
AU  - Wouter Cames van Batenburg
AU  - Quentin Claus
AU  - Gwenaël Joret
AU  - Robin Petit
AU  - Jean-Florent Raymond
AU  - Eileen Robinson
PY  - 2026
DA  - 2026/09/14
PB  - arXiv
DO  - 10.48550/arxiv.2609.15596
UR  - https://arxiv.org/abs/2609.15596
AB  - We show that every planar graph with no t × t grid minor has treewidth at most 4t +4. This improves on the previously best known bound of 9/2t − 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.
ER  -