The rank-width of the square grid

Rank-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 x n square grid, denoted by G(n,n), is a graph on the vertex set {1, 2, ... , n} x {1, 2, ... , n}, where a vertex (x, y) is connected by an edge to a vertex (x', y') if and only if vertical bar x - x'vertical bar + vertical bar y - y'vertical bar = 1. We prove that the rank-width of G(n,n) is equal to it n - 1, thus solving an open problem of Oum. (c) 2009 Elsevier B.V. All rights reserved.