Consecutive-ones: handling lattice planarity efficiently

Note the PDF in internal reference corrects some typographic bugs of the proceedingsInternational audienceA concept lattice may have a size exponential in the number of objects it models. Polynomial-size lattices and/or compact representations are thus desirable. This is the case for planar concept lattices, which has both polynomial size and representation without edge crossing, but a generic process for drawing them efficiently is yet to be found. Recently, it has been shown that when the relation has the consecutive-ones property (i.e, the matrix of the relation can be rapidly reorderd so that the 1s are consecutive in every row), the number of concepts is polynomial and these can be efficiently generated. In this paper we show that a consecutive-ones relation R has a planar lattice which can be drawn in O(|R|) time. We also give a hierarchical classification of polynomial-size lattices based on structural properties of the relation Rel, its associated graphs G_bip and G_R, and its concept lattice L_R