# Rank-width

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Rank-width
> Markdown URL: https://mediated.wiki/source/Rank-width.md
> Source: https://en.wikipedia.org/wiki/Rank-width
> Source revision: 1341255764
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

{{Short description|Graph width parameter used in graph theory}}
{{For|the computer memory concept|Memory rank}}
'''Rank-width''' is a graph width parameter used in [graph theory](/source/graph_theory) and [parameterized complexity](/source/parameterized_complexity), and defined using [linear algebra](/source/linear_algebra).

It is defined from hierarchical clusterings of the vertices of a given graph, which can be visualized as [ternary tree](/source/ternary_tree)s having the vertices as their leaves. Removing any edge from such a tree disconnects it into two subtrees and partitions the vertices into two subsets. The graph edges that cross from one side of the partition to the other can be described by a [biadjacency matrix](/source/biadjacency_matrix); for the purposes of rank-width, this matrix is defined over the [finite field](/source/finite_field) [GF(2)](/source/GF(2)) rather than using [real number](/source/real_number)s. The rank-width of a graph is the maximum of the [ranks](/source/Rank_(linear_algebra)) of the biadjacency matrices, for a clustering chosen to minimize this maximum.{{r|os}}

Rank-width is closely related to [clique-width](/source/clique-width): <math> k \leq c \leq 2^{k+1}-1</math>, where <math>c</math> is the clique-width and <math>k</math> the rank-width. However, clique-width is [NP-hard](/source/NP-hard) to compute, for graphs of large clique-width, and its [parameterized complexity](/source/parameterized_complexity) is unknown. In contrast, testing whether the rank-width is at most a constant <math>k</math> takes [polynomial time](/source/polynomial_time), and even when the rank-width is not constant it can be approximated, with a constant [approximation ratio](/source/approximation_ratio), in polynomial time. For this reason, rank-width can be used as a more easily computed substitute for clique-width.{{r|os}}

An example of a family of graphs with high rank-width is provided by the square [grid graph](/source/grid_graph)s. For an <math>n\times n</math> grid graph, the rank-width is exactly <math>n-1</math>.{{r|j}}

Trees have rank-width at most 1, and the graphs with rank-width at most 1 are precisely [distance-hereditary graphs](/source/Distance-hereditary_graph).<ref>{{Cite journal |last=Oum |first=Sang-il |date=2005-09-01 |title=Rank-width and vertex-minors |url=https://www.sciencedirect.com/science/article/pii/S0095895605000389 |journal=Journal of Combinatorial Theory, Series B |volume=95 |issue=1 |pages=79–100 |doi=10.1016/j.jctb.2005.03.003 |issn=0095-8956|url-access=subscription }}</ref> Graphs of small rank-width are precisely [pivot-minors](/source/Local_complementation) of graphs of small [tree-width](/source/Treewidth).<ref>{{Cite journal |last=Kwon |first=O-joung |last2=Oum |first2=Sang-il |date=2014-05-11 |title=Graphs of small rank-width are pivot-minors of graphs of small tree-width |url=https://www.sciencedirect.com/science/article/pii/S0166218X13000310 |journal=Discrete Applied Mathematics |series=Fifth Workshop on Graph Classes, Optimization, and Width Parameters, Daejeon, Korea, October 2011 |volume=168 |pages=108–118 |doi=10.1016/j.dam.2013.01.007 |issn=0166-218X|arxiv=1203.3606 }}</ref> A connected graph G with <math>n</math> vertices and <math>m</math> edges has a rank-width of at most <math> m-n+2</math>. A simple proof is to consider a spanning tree and note that trees have rank-width 1. Adding an edge to a graph increases the cut-rank function by at most 1 which increases the rank-width by at most 1, so adding the <math> m-n+1</math> extra edges to the spanning tree increases the rank-width by at most <math> m-n+1</math>.

==References==
<references>

<ref name=j>{{citation
 | last = Jelínek | first = Vít
 | doi = 10.1016/j.dam.2009.02.007
 | issue = 7
 | journal = [Discrete Applied Mathematics](/source/Discrete_Applied_Mathematics)
 | mr = 2602833
 | pages = 841–850
 | title = The rank-width of the square grid
 | volume = 158
 | year = 2010| doi-access = free
 }}</ref>

<ref name=os>{{citation
 | last1 = Oum | first1 = Sang-il
 | last2 = Seymour | first2 = Paul
 | doi = 10.1016/j.jctb.2005.10.006
 | issue = 4
 | journal = Journal of Combinatorial Theory, Series B
 | mr = 2232389
 | pages = 514–528
 | title = Approximating clique-width and branch-width
 | volume = 96
 | year = 2006| citeseerx = 10.1.1.139.9829
 }}</ref>

</references>

Category:Graph minor theory
Category:Linear algebra

{{graph-stub}}

---
Adapted from the Wikipedia article [Rank-width](https://en.wikipedia.org/wiki/Rank-width) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Rank-width?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.