  We design two incremental algorithms for computing an inclusion-minimal
completion of an arbitrary graph into a cograph. The first one is able to do so
while providing an additional property which is crucial in practice to obtain
inclusion-minimal completions using as few edges as possible : it is able to
compute a minimum-cardinality completion of the neighbourhood of the new vertex
introduced at each incremental step. It runs in $O(n+m')$ time, where $m'$ is
the number of edges in the completed graph. This matches the complexity of the
algorithm in [Lokshtanov, Mancini and Papadopoulos 2010] and positively answers
one of their open questions. Our second algorithm improves the complexity of
inclusion-minimal completion to $O(n+m\log^2 n)$ when the additional property
above is not required. Moreover, we prove that many very sparse graphs, having
only $O(n)$ edges, require $\Omega(n^2)$ edges in any of their cograph
completions. For these graphs, which include many of those encountered in
applications, the improvement we obtain on the complexity scales as $O(n/\log^2
n)$.
