On computing the Galois Lattice of Bipartite Distance Hereditary graphs

The class of Bipartite Distance Hereditary (BDH) graphs is the intersection between bipartite domino-free and chordal bipartite graphs. Graphs in both the latter classes have linearly many maximal bicliques, implying the existence of polynomial-time algorithms for computing the associated Galois lattice. Such a lattice can indeed be built in O(m?n)O(m?n)worst-case time for a domino-free graph with mm edges and nn vertices. In Apollonio et al. (2015), BDH graphs have been characterized as those bipartite graphs whose Galois lattice is tree-like. In this paper we give a sharp upper bound on the number of maximal bicliques of a BDH graph and we provide an O(m)O(m) time-worst-case algorithm for incrementally computing its Galois lattice. The algorithm in turn implies a constructive proof of the if part of the characterization above. Moreover, we give an O(n)O(n) worst-case space and time encoding of both the input graph and its Galois lattice, provided that the reverse of a Bandelt and Mulder building sequence is given.