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.

Type

Journal article

Intellectual base

Primary research

Year

1998

DOI

10.1016/s0304-3975(97)00228-4

Link

https://doi.org/10.1016/S0304-3975(97)00228-4

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.

• Pathwidth
  • Approximation, fixed-parameter recognition, and forbidden-minor theorems are results about the invariant rather than parts of its definition.

Verification

This reference passed the adversarial substantiation pipeline: it was checked to exist and to support the claim it is attached to. See how references were verified.

Registry ID ref:71ffd747228b · see in the full table