A Partial k-Arboretum of Graphs with Bounded Treewidth¶
Bodlaender, H. L. (1998). A Partial k-Arboretum of Graphs with Bounded Treewidth. Theoretical Computer Science, 209(1–2), 1-2.
Cited by¶
2 citations across 2 artifacts.
Each citation links to the sentence it supports in the citing article.
Domain-specific¶
- Partial k-tree
- Large planar grids have unbounded treewidth, and bounded-treewidth classes at suitable k include nonplanar graphs
This sourceThe converse observation, that bounded-treewidth classes contain nonplanar graphs, is not drawn there. Bodlaender's survey states the characterization directly: a graph has treewidth at most 1 exactly when it has no K3 minor - one obstruction, against four already at k = 3. Bodlaender's survey carries both halves - treewidth at most 2 is exactly the partial 2-trees, and the class is precisely the K4-minor-free graphs - and, in the same theorem set, the componentwise series-parallel formulation. Bodlaender's survey gives the value under the same n-by-n indexing the sentence uses, proving the lower bound as Lemma 88; the hedge is about competing grid conventions elsewhere, not a disagreement with this source.
Supported in partVerified against the source
- Large planar grids have unbounded treewidth, and bounded-treewidth classes at suitable k include nonplanar graphs
- Pathwidth
Verification¶
Does it exist? Confirmed. This work's DOI resolves to a registered record, which fixes its identity. That is all it fixes.
Does it back the claim? Read against the text for 1 of 2 citations: 1 supported in part. Each verdict is shown under its citation below, with what in the work backs the sentence.
Support is checked per citation rather than per work — the same source can be cited soundly in one article and wrongly in another. Per-citation recording began recently, so a citation with no recorded check is a gap in the record rather than evidence it went unchecked.
See how references were verified.
Registry ID ref:71ffd747228b · see in the full table