=Paper=
{{Paper
|id=Vol-110/paper-13
|storemode=property
|title=Planarity of Additively Drawn Concept Lattices
|pdfUrl=https://ceur-ws.org/Vol-110/paper14.pdf
|volume=Vol-110
|dblpUrl=https://dblp.org/rec/conf/cla/Zschalig04
}}
==Planarity of Additively Drawn Concept Lattices==
https://ceur-ws.org/Vol-110/paper14.pdf
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.