Open Research Index

Optimal tree-decompositions with bags of bounded pathwidth

Kevin Hendrey, Robert Hickingbotham, Jędrzej Hodor, David R. Wood

arXivarxiv/2607.27601Jul 30, 2026math.COscore 0

We show that every planar graph has a tree-decomposition with optimal width such that the subgraph induced by each bag has pathwidth at most 3. This bound is best possible, and for tree-decompositions that satisfy a certain minimality condition, we in fact give a precise description of the possible structures in each bag. Moreover, we show that the union of any $k$ bags has pathwidth $O(k)$. We also show that graphs excluding a fixed double-apex-forest minor have a tree-decomposition with optimal width such that the subgraph induced by each bag has bounded pathwidth. This includes graphs…

SourceJSON

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2607.27601
curl -X POST /api/v1/records/arxiv/2607.27601/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2607.27601/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'