Vertex-minor reductions can simulate edge contractions

We prove that local complementation and vertex deletion, operations from which vertex-minors are defined, can simulate edge contractions. As an application, we prove that the rank-width of a graph is linearly bounded in term of its tree-width.     

On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width

Rank-width is a structural graph measure introduced by Oum and Seymour and aimed at better handling of graphs of bounded clique-width. We propose a formal mathematical framework and tools for easy design of dynamic algorithms running directly on a rank-decomposition of a graph (on contrary to the usual approach which translates a rank-decomposition into a clique-width expression, with a possible exponential jump in the parameter). The main advantage of this framework is a fine control over the runtime dependency on the rank-width parameter. Our new approach is linked to a work of Courcelle and Kanté [7] who first proposed algebraic expressions with a so-called bilinear graph product as a better way of handling rank-decompositions, and to a parallel recent research of Bui-Xuan, Telle and Vatshelle.     

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×nsquare grid, denoted by G_n,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 G_n,n is equal to n−1, thus solving an open problem of Oum.