Animation scientifique

Merge-width is a recently introduced family of graph parameters that unifies treewidth, clique-width, twin-width, and generalised colouring numbers. We prove the equivalence of several alternative definitions of merge-width, thus demonstrating the robustness of the notion. Our characterisation via definable merge-width uses vertex orderings inspired by generalised colouring numbers from sparsity theory, and enables us to obtain the first non-trivial approximation algorithm for merge-width, running in time n^O(1)·2^n. Using these alternative definition we also establish that graphs of bounded merge-width admit sparse quotients with bounded strong colouring numbers, are quasi-isometric to graphs of bounded expansion, and admit neighbourhood covers with constant overlap.