Characterizing width two for variants of treewidth

DOI10.1016/J.DAM.2015.01.015MaRDI QIDQ344827zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Hans L. Bodlaender, Stefan Kratsch, Vincent J. C. Kreuzen, Seongmin Ok, O-joung Kwon

Publication date 24 November 2016

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1404.3155

zbMATH Keywords

treewidthminorspaghetti treewidthspecial treewidthstrongly chordal treewidth

Mathematics Subject Classification ID

Trees (05C05) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: In this paper, we consider the notion of emph{special treewidth}, recently introduced by Courcellecite{Courcelle2012}. In a special tree decomposition, for each vertex $v$ in a given graph, the bags containing $v$ form a rooted path. We show that the class of graphs of special treewidth at most two is closed under taking minors, and give the complete list of the six minor obstructions. As an intermediate result, we prove that every connected graph of special treewidth at most two can be constructed by arranging blocks of special treewidth at most two in a specific tree-like fashion. Inspired from the notion of special treewidth, we introduce three natural variants of treewidth, namely emph{spaghetti treewidth}, emph{strongly chordal treewidth} and emph{directed spaghetti treewidth}. All these parameters lie between pathwidth and treewidth, and we provide common structural properties on these parameters. For each parameter, we prove that the class of graphs having the parameter at most two is minor closed, and we characterize those classes in terms of a emph{tree of cycles} with additional conditions. Finally, we show that for each $kgeq3$, the class of graphs with special treewidth, spaghetti treewidth, directed spaghetti treewidth, or strongly chordal treewidth, respectively at most $k$, is not closed under taking minors.

Recommendations

• Fixed-parameter tractability and characterizations of small special treewidth
• The structure of obstructions to treewidth and pathwidth
• Tree-decompositions of small pathwidth
• On 3-connected graphs of path-width at most three
• The Structure and Number of Obstructions to Treewidth

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 176761 (Why is no real title available?)
• scientific article; zbMATH DE number 1323192 (Why is no real title available?)
• A Simple Linear Time Algorithm for Triangulating Three-Colored Graphs
• A characterization of partial 3-trees
• A partial k-arboretum of graphs with bounded treewidth
• A recognition algorithm for the intersection graphs of paths in trees
• Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
• Characterizations of strongly chordal graphs
• Edge and vertex intersection of paths in a tree
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• Fixed-parameter tractability and characterizations of small special treewidth
• Forbidden graphs for tree-depth
• Forbidden minors characterization of partial 3-trees
• Graph Classes: A Survey
• Graph minors. I. Excluding a forest
• Graph minors. II. Algorithmic aspects of tree-width
• Graph minors. XX: Wagner's conjecture
• Graph theory
• Intersection graphs of paths in a tree
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• Neighborhood subtree tolerance graphs
• Nondeterministic graph searching: from pathwidth to treewidth
• Obstruction set isolation for the gate matrix layout problem
• On intervalizing \(k\)-colored graphs for DNA physical mapping
• On the model-checking of monadic second-order formulas with edge set quantifications
• On the structure of graphs with path-width at most two
• Rankings of Graphs
• The forbidden subgraph characterization of directed vertex graphs
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• The vertex separation and search number of a graph
• Treewidth. Computations and approximations

Cited in

(5)

• Finding cut-vertices in the square roots of a graph
• Characterizing graphs of maximum matching width at most 2
• From tree-decompositions to clique-width terms
• LATIN 2004: Theoretical Informatics
• Fixed-parameter tractability and characterizations of small special treewidth

This page was built for publication: Characterizing width two for variants of treewidth

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q344827)