Fig. 4From: A safe and complete algorithm for metagenomic assemblyAn extremal graph G showing that the upper bound on the complexity of Algorithm 1 from Theorem 12 is attained. The vertex set of G is \(\{a_1,\dots ,a_{n/2},b_1,\dots ,b_{n/2}\}\). Any node- or edge-covering metagenomic reconstruction of G consists of circular walk(s) whose total length is \(\Omega (n^2)\)Back to article page