Rank-width: Algorithmic and structural results

Abstract

Rank-width is a width parameter of graphs describing whether it is possible to decompose a graph into a tree-like structure by `simple' cuts. This survey aims to summarize known algorithmic and structural results on rank-width of graphs.

arXiv comment14 pages; minor revision

References in corpus (10)

• Rank-width and Tree-width of H-minor-free Graphs
• Faster Algorithms For Vertex Partitioning Problems Parameterized by Clique-width
• Rank-width of Random Graphs
• Excluded vertex-minors for graphs of linear rank-width at most k
• Partitions versus sets : a case of duality
• Rank-width and Well-quasi-ordering of Skew-Symmetric or Symmetric Matrices
• Graphs of Small Rank-width are Pivot-minors of Graphs of Small Tree-width
• Number of cliques in graphs with a forbidden subdivision
• Well-Quasi-Ordering of Matrices under Schur Complement and Applications to Directed Graphs
• Fast Matrix Rank Algorithms and Applications

Cited by in corpus (16)

• Quantum network routing and local complementation
• Photonic resource state generation from a minimal number of quantum emitters
• Clique-Width for Hereditary Graph Classes
• The grid theorem for vertex-minors
• Obstructions for bounded shrub-depth and rank-depth
• Sharp complexity phase transitions generated by entanglement
• Partial complementation of graphs
• List $k$-Colouring $P_t$-Free Graphs: a Mim-width Perspective
• Tangled up in Blue (A Survey on Connectivity, Decompositions, and Tangles)
• Rank connectivity and pivot-minors of graphs
• Scattered classes of graphs
• Generating graph states with a single quantum emitter and the minimum number of fusions
• Graphs of bounded depth-$2$ rank-brittleness
• Intertwining connectivities for vertex-minors and pivot-minors
• Tree pivot-minors and linear rank-width
• Covering a Graph with Minimal Local Sets