On NC algorithms for problems on bounded rank-width graphs

In this paper, we show that for a fixed k, there is an NC algorithm that separates the graphs of rank-width at most k from those with rank-width at least 3k+1.