Rank‐width is less than or equal to branch‐width

DOI10.1002/JGT.20280zbMath1135.05059OpenAlexW4252418493WikidataQ131629229 ScholiaQ131629229MaRDI QIDQ5450349

Sang-il Oum

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

zbMATH Keywords

incidence graphsline graphsclique-widthtree-widthrank-widthbranch-width

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Combinatorial aspects of matroids and geometric lattices (05B35)

Related Items (24)

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 ⋮ Vertex-minors of graphs: a survey ⋮ 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

This page was built for publication: Rank‐width is less than or equal to branch‐width