Rank‐width is less than or equal to branch‐width
From MaRDI portal
Publication:5450349
DOI10.1002/jgt.20280zbMath1135.05059OpenAlexW4252418493MaRDI QIDQ5450349
Publication date: 20 March 2008
Published in: Journal of Graph Theory (Search for Journal in Brave)
Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.107.6768
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Combinatorial aspects of matroids and geometric lattices (05B35)
Related Items
Rank-width of random graphs ⋮ Approximate tree decompositions of planar graphs in linear time ⋮ The Rank-Width of the Square Grid ⋮ Rank-width: algorithmic and structural results ⋮ On quasi-planar graphs: clique-width and logical description ⋮ From tree-decompositions to clique-width terms ⋮ Tangle bases: Revisited ⋮ Classes of intersection digraphs with good algorithmic properties ⋮ Inapproximability of rank, clique, Boolean, and maximum induced matching-widths under small set expansion hypothesis ⋮ Graphs of small rank-width are pivot-minors of graphs of small tree-width ⋮ Faster algorithms for vertex partitioning problems parameterized by clique-width ⋮ Branch-depth: generalizing tree-depth of graphs ⋮ Vertex-minor reductions can simulate edge contractions ⋮ \(H\)-join decomposable graphs and algorithms with runtime single exponential in rankwidth ⋮ The rank-width of the square grid ⋮ Rank-width and tree-width of \(H\)-minor-free graphs ⋮ Boolean-width of graphs ⋮ On the Boolean-Width of a Graph: Structure and Applications ⋮ On low rank-width colorings ⋮ Graph operations characterizing rank-width ⋮ Boolean-Width of Graphs ⋮ Unnamed Item ⋮ Canonisation and Definability for Graphs of Bounded Rank Width
