Computing rank-width exactly

We prove that the rank-width of an n-vertex graph can be computed exactly in time O(n2n3log2nloglogn). To improve over a trivial O(n3logn)-time algorithm, we develop a general framework for decompositions on which an optimal decomposition can be computed efficiently. This framework may be used for other width parameters, including the branch-width of matroids and the carving-width of graphs.