Vertical decomposition of a lattice using clique separators
Anne Berry, Romain Pogorelcnik, Alain Sigayret · Concept Lattices and their Applications · 2011
A concept (or Galois) lattice is built on a binary relation; this relation can be represented by a bipartite graph. We explain how we can use the graph tool of clique minimal separator decomposition to decom- pose some bipartite graphs into subgraphs in linear time; each subgraph corresponds to a subrelation. We show that the lattices of these subrela- tions easily yield the lattice of the global relation. We also illustrate how this decomposition is a tool to help displaying the lattice.