The rank-width of the square grid

AbstractRank-width is a graph width parameter introduced by Oum and Seymour. It is known that a class of graphs has bounded rank-width if, and only if, it has bounded clique-width, and that the rank-width of G is less than or equal to its branch-width.The n×n square grid, denoted by Gn,n, is a graph on the vertex set {1,2,…,n}×{1,2,…,n}, where a vertex (x,y) is connected by an edge to a vertex (x′,y′) if and only if |x−x′|+|y−y′|=1.We prove that the rank-width of Gn,n is equal to n−1, thus solving an open problem of Oum