In Formal Concept Analysis, it is a very important but quite difficult task to draw line diagrams of concept lattices automatically. In particular, we want every planar lattice to be visualized without edge crossings. Many algorithms ignore that fact or find plane diagrams only heuristically. We present a characterization of planar lattices based on the theorem of Baker, Fishburn and Roberts [1] and the ”left”-relation introduced by Rival [5]. In particular, our work is helpful for drawing attribute- (or dually object-) additive diagrams.
In the following we always deal with finite lattices. As we are interested in algorithms for visualizing lattices, this seems to be sufficient. When speaking about contexts, we always mean reduced ones. By a diagram of a lattice V we actually mean an upward line diagram, which is denoted by pos(V).
One base of our work is the theorem of Baker, Fishburn and Roberts [1]: Theorem 1 A lattice is planar if and only if it has an order dimension of at most two.
This theorem allows us to characterize planar lattices by interval-inclusionlattices (IIL).
Definition 2 A lattice V is an IIL, if V =∼ (I, ⊆) holds for a subset I ⊆ I(R). The set I(R) denotes the set of all closed intervals in R. Corollary 3 [4] A finite lattice is planar if and only if it is isomorphic to an IIL.
When drawing lattices, most people tend to use (at least partially) the convention of attribute (or dually object) additivity, even if they do not know what it actually is. This method is useful mainly for distributive (or ”nearly distributive”) lattices, as the resulting diagrams look like drawn on an n-dimensional grid [6].
Definition 4 Let B(G, M, I) be a concept lattice. A diagram pos(B(G, M, I)) is attribute additive, if there is a map vec : M 7→ R2, such that the equation pos(c) =
X m∈Int(c) vec(m) holds for all concepts c ∈ B(G, M, I). 3
In the following, we introduce binary relations L(V) and L(pos(V)) (L is an abbreviation for ”left”) on elements of lattices V and nodes of line diagrams pos(V). Dually, we can consider a relation R (which stands for ”right”) and naturally assume, that eLf ⇐⇒ f Re holds for e, f being arbitrary lattice elements or diagram nodes respectively. 3.1
When having a closer look on IILs, we can easily give a definition for an interval being left of another one.
Definition 5 Let I be an IIL. Two elements [il, ir], [jl, jr] ∈ I are in L-relation, if the conditions il < jl and ir < jr hold.
Obviously, this relation is a strict order. We also notice, that two intervals are in L-relation, if and only if they are incomparable. Indeed we can proof that any finite lattice posessing a relation, which fulfills these requirements is planar already.
Corollary 6 A lattice V = (V, ≤) is planar, if and only if there is a binary relation L on V, such that the below-mentioned conditions hold:
L is a strict order.
L ∪ L−1 = k
(
We conclude that L< is a linear strict order. By applying analogous argumentation, we realize that R< is a linear strict order too. Additionally we see the identity L< ∩ R< = <. Hence the order dimension of V is at most two and with Theorem 1 we conclude that V is planar.
How can we find L-relations fulfilling the conditions from corollary 6? We come back to the already mentioned attributive additive approach. First we describe that relation only for attribute concepts with commom upper neighbour. Here the effect of a node v being left of another node w is intuitively understandable: in an appropriate diagram the line connecting v with its upper neighbour v∗ should be left of the line connecting w and v∗. However, now we are interested only in lattices and not yet in diagrams, so the following definitions will be more abstract.
Definition 7 Let B(G, M, I) be a concept lattice. A relation La ⊆ M × M is called sorting relation, if the following condition holds for all attributes mi, mj ∈ M :
μmi∗ = μmj∗ ⇐⇒ either miLamj or mj Lami holds.
Now we extend the sorting relation to a bigger domain.
Definition 8 Let B(G, M, I) be a concept lattice with given sorting relation La. For arbitrary lattice elements v and w, we define M (v, w) = (Int(v) \ Int(w)) × (Int(w)\Int(v)). We define the relation L ⊆ B(G, M, I)×B(G, M, I) as follows: 1. miLamj =⇒ μmiLμmj 2. If for attribute concepts, μmi∗ 6= μmj∗ holds,
μmiLμmj : ⇐⇒ ∃(mk, ml) ∈ M (mi, mj ) \ {(mi, mj )} : μmkLμml. 3. After L is computed on all pairs of attribute concepts,
vLw : ⇐⇒ ∃(mi, mj) ∈ M (v, w) : μmiLμmj.
Without proof, we give as a first result, that the above defined relation fulfills
condition (
v1Lw1 ∧ (v1, w1) ∈ M (v2, w2) =⇒ v2Lw2 Proof. We assume w2Lv2. Since (v1, w1) ∈ M (v2, w2) we know, that v1 and w2 are incomparable. We conclude either v1Lw2 and v1Lv2, since L is transitive, or w2Lv1 and v2Lv1. Both cases lead to a contradiction, since v1 and v2 are comparable.
The lemmata 9 and 10 point out, that the relations L are the only ones which may lead to a planar lattice. This gives us an (albeit very slow) algorithm to check whether a lattice is planar: Compute the L-relations from all possible sorting relations (at most |M |!) and check, whether they are strict orders. 3.2
In the previous subsection we gave an idea how to define an additional relation L in a lattice to check, whether it is planar. Now we want to give a method to actually embed a planar lattice into the plane, if the relation L is given. First we have to define how this relation is to be found in a diagram.
Definition 11 Let B(G, M, I) be a concept lattice with a diagram pos(B(G, M, I)). The sorting relation La(pos(B(G, M, I))) ⊆ pos(M ) × pos(M ) is defined as follows (ϕ(e) denotes the angle of the line e.): pos(mi)Lapos(mj ) : ⇐⇒
mi∗ = mj∗ ∧ ϕ(pos(mi) − pos(mi∗)) < ϕ(pos(m2) − pos(m2∗)).
This definition is indeed very similar to definition 7. Every sorting relation in a diagram defines a sorting relation on the underlying lattice, and every sorting relation in a lattice can be realized in a diagram. Now we again extend this relation to an L-relation such that L ∪ L−1 = k: Definition 12 Let B(G, M, I) be a concept lattice with a diagram pos(B(G, M, I)). Let p = 0B(G,M,I) . . . 1B(G,M,I) be an arbitrary chain from bottom to top. We denote with Fl(p) the area left of p and with Fr(p) the area right of p. We define the binary relation L, such that
vLw : ⇐⇒ (∃p 3 w : v ∈ Fl(p)) ∧ (v k w) holds for all diagram nodes v and w.
This definition is quite similar to the one I. Rival gave in [5] 1. In figure 1 we provide two examples for the L-relation of of a diagram.
After these preparations we come to the main result of that work. It gives a possibility to actually draw a plane diagram of a planar lattice, where the relation L is conserved. 1 The differences are due to make this definiton compatible to the one of L-relations in lattices. a c b d e
Theorem 13 Let B(G, M, I) be a concept lattice, La a sorting relation in B(G, M, I) and L the associated L-relation. The following statements are equivalent: 1. There exists a plane diagram with the sorting relation
La(pos(B(G, M, I))) = pos(La(B(G, M, I))) 2. L is a strict order.
Proof. ”⇐”: By using the relations L< and R< from the proof of corollary 6 we can define a map ψ : B(G, M, I) 7→ I, where I is a IIL, by ψ : v 7→ [ψl(v), ψr(v)], where the mappings ψl, ψr : B(G, M, I) 7→ R meet the conditions
vL<w =⇒ ψr(v) < ψr(w) and vR<w =⇒ ψl(w) < ψl(v).
We can easily show, that ψ is an isomorphism between (B(G, M, I), ≤, L) and (I, ⊆, L˜), where L˜ is the above-defined ”left”-relation for IILs. We define another map pos : ψ(B(G, M, I)) 7→ R2 by pos([x, y]) := (x, y). Now we can proof, that the diagram pos(ψ(B(G, M, I))) is plane and that its sorting relation is the restriction of L. 1. pos(ψ(B(G, M, I))) does not contain an edge crossing: We assume, that the diagram edges corresponding to the elements v1 ≺ v3 and v2 ≺ v4 cross. Let (xi, yi) the coordinates of the node vi and (x5, y5) be the coordinates of the intersection. With the definition of ψ we conclude x3, x4 < x5 < x1, x2 and y1, y2 < y5 < y3, y4, i.e. v2 < v3 and v1 < v4. That means, that v3 and v4 do not have an infimum in contradiction to B(G, M, I) being a lattice. 2. pos(ψ(B(G, M, I)) is an upward drawing: this is obviously satisfied by the definitions of pos and ψ. 3. Let miLamj for two attributes in M . Let (xi, yi) and (xj , yj ) be the coordinates of the appropriate diagram nodes and (x, y) the coordinates of their common upper neighbour. Then the inequalities x < xi < xj and y1 < y2 < y hold. For the angles ϕi := ϕ(pos(μmi) − pos(μmi∗)) and ϕj := ϕ(pos(μmj ) − pos(μmj∗)) we get tan ϕi = yi − y and tan ϕj = yj − y .
xi − x xj − x it arises yi − y < yj − y < 0 and 0 < xi < xj , i.e. tan ϕi < tan ϕj . The angles are in the intervall (3/2 · π, π). In this domain the function arctan is monotonous, so we conclude ϕi < ϕj , i.e. pos(mi)Lapos(mj ). ”⇒”: 1. L(pos(B(G, M, I))) is irreflexive by definition. 2. We assume z1Lz2 and z2Lz1 for two diagram nodes z1, z2. Then we find two chains p1 = pos(0B(G,M,I)) . . . z1 . . . pos(1B(G,M,I)) and p2 = pos(0B(G,M,I)) . . . z2 . . . pos(1B(G,M,I)) such that p1 and p2 intersect. Since the diagram is plane, the point of intersection is again a node in contradiction of the concepts corresponding to z1 and z2 not being comparable.
Hence L is antisymmetric. 3. In an analogous way we can show L to be transitive. 4. Every two incomparable nodes are in L-relation: this is obviously granted by definition. 5. If pos(mi)Lapos(mj ) holds for two attribute concepts, we have ϕ(pos(mi)) < ϕ(pos(mj )) and pos(μmi)Lpos(μmj ) respectively.
By lemma 10 and 5 we conclude that L(pos(B(G, M, I))) is the corresponding L-relation to La. Additionally, we showed that L is a strict order. 4
We have shown in this work, that the relationship of attribute concepts indeed provides an instrument to characterize, whether the associated concept lattice is planar. Unfortunately an efficient algorithm using that connection is not developed yet. Such an algorithm would be very useful for a lattice layout program using the attribute (or dually object) additive convention for quick planarity testing and embedding. The next steps to do are: – Find a fast algorithm to compute all planar sorting relations. – Classify plane diagrams of a lattice up to homeomorphisms.
– Proof that every planar lattice posesses a plane attribute additive diagram.