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.

14 pages; minor revision

References in corpus (1)

• Partitions versus sets : a case of duality

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