Characterizing width two for variants of treewidth

DOI10.1016/J.DAM.2015.01.015zbMATH Open1350.05116DBLPjournals/dam/BodlaenderKKKO17arXiv1404.3155OpenAlexW2084535634WikidataQ59567366 ScholiaQ59567366MaRDI QIDQ344827FDOQ344827

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

Publication date: 24 November 2016

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

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.

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

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

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)

Cites Work

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

Cited In (4)

• From tree-decompositions to clique-width terms
• Characterizing graphs of maximum matching width at most 2
• Finding cut-vertices in the square roots of a graph
• LATIN 2004: Theoretical Informatics

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)