A Peep through the Looking Glass: Articulation Points in Lattices

摘要

We define as an 'articulation point' in a lattice an element which is comparable to all the other elements, but is not extremum. We investigate a property which holds for both the lattice of a binary relation and for the lattice of the complement relation (which we call the mirror relation): one has an articulation point if and only if the other has one also. We give efficient algorithms to generate all the articulation points. We discuss artificially creating such an articulation point by adding or removing crosses of the relation, and also creating a chain lattice. We establish the strong relationships with bipartite and co-bipartite graphs; in particular, we derive efficient algorithms to compute a minimal triangulation and a maximal sub-triangulation of a co-bipartite graph, as well as to find the clique minimal separators and the corresponding decomposition.