About: Rank-width

Rank-width is a graph width parameter used in graph theory and parameterized complexity. This parameter indicates the minimum integer k for a given graph G so that the tree can be decomposed into tree-like structures by splitting its vertices such that each cut induces a matrix of rank at most k. Even though there are various other width parameters that have been shown to be very useful, but some of them like treewidth (or clique-width) are bounded for only for sparse (or dense) graphs. For the dense graphs, where clique-width can be used, there is no efficient algorithm deciding this parameter. This is where rank-width comes to the picture. There exists an algorithm running in polynomial time that decides if the rank-width of an input graph is at most k.