Planarity Planarity of of Additively Additively Drawn Drawn Concept Concept Lattices Lattices Christian Zschalig Christian Zschalig Institute of Algebra, TU Dresden, Germany Institute of Algebra, TU Dresden, Germany zschalig@math.tu-dresden.de zschalig@math.tu-dresden.de Abstract. 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. 1 Motivation There exist algorithms for embedding lattices into the plane already, see [2] for an overview. These algorithms do not use the lattice structure, but more general ones (graphs or acyclic digraphs) for the characterisation of planar lattices. We want to use the convention of attribute-additively drawn diagrams [3], because it provides nice visualizations of lattices. By applying this rule, the coordinates of the nodes of the attribute concepts (denoted by attribute vector in the following) define the coordinates of all other nodes. Hence the relationship of the attribute vectors in the plane appears to characterize the planarity of the diagram. 2 Introduction 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-inclusion- lattices (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. c V. Snášel, R. Bělohlávek (Eds.): CLA 2004, pp. 137–142, ISBN 80-248-0597-9. VŠB – Technical University of Ostrava, Dept. of Computer Science, 2004. 2138 Christian Zschalig 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 con- vention 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 distribu- tive”) 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 X pos(c) = vec(m) m∈Int(c) holds for all concepts c ∈ B(G, M, I). 3 The L-Relation 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 The L-Relation on Lattices 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. (1) L ∪ L−1 = k (2) Proof. ”⇒”: This can be derived immediately from Theorem 3 and Definition 5. ”⇐”: Consider the relations L< := L ∪ < and R< := R ∪ <. We show the following properties: Planarity of Additively Drawn Concept Lattices 139 3 1. L< is connex because of condition (2). 2. L< is irreflexive, since L and < are irreflexive. 3. From vL< w and wL< v follows neither vLw and wLv nor v < w and w < v, since L and < are orders. The remaining cases infringe condition (2). Hence L< is antisymmetric. 4. Assume vL< wL< zL< v. Since L and < are strict orders, we conclude w.l.o.g. vLw < z. This is contrary to condition 2, since we have either z < v, i.e. w < v or zLv, i.e. zLw. Hence L< is transitive. We conclude that L< is a linear strict order. By applying analogous argumen- tation, 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 m i , mj ∈ M: µm∗i = µm∗j ⇐⇒ either mi La mj or mj La mi 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 L a . 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. mi La mj =⇒ µmi Lµmj 2. If for attribute concepts, µm∗i 6= µm∗j holds, µmi Lµmj : ⇐⇒ ∃(mk , ml ) ∈ M (mi , mj ) \ {(mi , mj )} : µmk Lµml . 3. After L is computed on all pairs of attribute concepts, vLw : ⇐⇒ ∃(mi , mj ) ∈ M (v, w) : µmi Lµmj . Without proof, we give as a first result, that the above defined relation fulfills condition (2) of corollary 6: Lemma 9 For the L-relation from definition 8, the identity L ∪ L−1 = k holds. On the other hand we can also proof, that the L-relation from definition 8 is (for a fixed sorting relation) the only one meeting the requirements of corollary 6. 4140 Christian Zschalig Lemma 10 Let B(G, M, I) be a concept lattice and L ⊆ B(G, M, I)×B(G, M, I) fulfilling the conditions (1) and (2). Then the following implication holds for all lattice elements v1 , v2 , w1 , w2 : v1 Lw1 ∧ (v1 , w1 ) ∈ M (v2 , w2 ) =⇒ v2 Lw2 Proof. We assume w2 Lv2 . Since (v1 , w1 ) ∈ M (v2 , w2 ) we know, that v1 and w2 are incomparable. We conclude either v1 Lw2 and v1 Lv2 , since L is transitive, or w2 Lv1 and v2 Lv1 . 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 The L-Relation on Diagrams 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 fol- lows (ϕ(e) denotes the angle of the line e.): pos(mi )La pos(mj ) : ⇐⇒ m∗i = m∗j ∧ ϕ(pos(mi ) − pos(m∗i )) < ϕ(pos(m2 ) − pos(m∗2 )). 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 de- note 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. Planarity of Additively Drawn Concept Lattices 141 5 L a b c d e L bc a d e a ×× × b × × a b e b a e b × c ××× c ×× a × c d c d d × d e e Fig. 1. Two diagrams of the same lattice with their L-relations. 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 equiv- alent: 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 mi La mj for two attributes in M . Let (xi , yi ) and (xj , yj ) be the co- ordinates 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(µm∗i )) and ϕj := ϕ(pos(µmj ) − pos(µm∗j )) we get yi − y yj − y tan ϕi = and tan ϕj = . xi − x xj − x 6142 Christian Zschalig 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 )La pos(mj ). ”⇒”: 1. L(pos(B(G, M, I))) is irreflexive by definition. 2. We assume z1 Lz2 and z2 Lz1 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 con- tradiction 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 )La pos(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 Results and Further Work 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 devel- oped 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. References 1. K. A. Baker, P. Fishburn, F. S. Roberts, Partial Orders of Dimension 2. Networks, 2, 11-28, 1971. 2. G. DiBattista, P. Eades, R. Tamassia, I. G. Tollis, Graph Drawing. Prentice Hall, 1999. 3. B. Ganter, R. Wille, Formal Concept Analysis. Springer, 1999. 4. J. Gross, J. Yellen, Graph Theory and its Applications. CRC Press, 1999. 5. I. Rival, Introducing Ordered Sets. http://www.site.uottawa.ca/dept/algorithms/order/, 1996. 6. M. Skorsky, Endliche Verbände - Diagramme und Eigenschaften. PhD thesis, TH Darmstadt, 1992.