Rank-width is a graph width parameter used in
graph theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...
and
parameterized complexity
In computer science, parameterized complexity is a branch of computational complexity theory that focuses on classifying computational problems according to their inherent difficulty with respect to ''multiple'' parameters of the input or output. T ...
. 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
Matrix most commonly refers to:
* ''The Matrix'' (franchise), an American media franchise
** ''The Matrix'', a 1999 science-fiction action film
** "The Matrix", a fictional setting, a virtual reality environment, within ''The Matrix'' (franchis ...
of
rank
Rank is the relative position, value, worth, complexity, power, importance, authority, level, etc. of a person or object within a ranking, such as:
Level or position in a hierarchical organization
* Academic rank
* Diplomatic rank
* Hierarchy
* H ...
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
In graph theory, the treewidth of an undirected graph is an integer number which specifies, informally, how far the graph is from being a tree. The smallest treewidth is 1; the graphs with treewidth 1 are exactly the trees and the forests. The gra ...
(or
clique-width
In graph theory, the clique-width of a graph is a parameter that describes the structural complexity of the graph; it is closely related to treewidth, but unlike treewidth it can be bounded even for dense graphs.
It is defined as the minimum num ...
) 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''.
The best known relationship between rank-width and clique-width is as follows:
, where ''c'' is the clique-width.
Graph minor theory
{{combin-stub