This paper presents an incremental algorithm to compute the covering graph of the lattice generated by a family B of subsets of a totally ordered set X . The implementation of this algorithm has O (((| X | + |B|).|B|).|F|) time complexity, where F is the number of elements in the lattice. This improves the complexity of the previous algorithms which is roughly in O ( Min (|X|, |B|) 3 .|F|). This algorithm may be used in many applications in computer sciences such as the computations of Galois (concept) lattice, the maximal antichains lattice or the Dedekind-MacNeille completion of a partial order. All these lattices can be computed incrementally using this algorithm without increasing time complexity.