Quick way of drawing Hasse diagrams of posets

600 Views Asked by At

When drawing a Hasse diagram, I have seen that you can draw a bigraph for the poset and remove the reflexive and transitive edges of the poset. However, doing this for a poset with many elements can get tedious (by hand).

Is there a more efficient way of drawing a Hasse diagram?

2

There are 2 best solutions below

0
On BEST ANSWER

This problem is known as transitive reduction. It is shown equivalent to multiplication of binary matrices. A simple $n^3$ algorithm (so pretty good in regards of matrix multiplication) is as follow : Compute the transitive closure then find transitive edges by iterating over all sets of 3 vertices.

0
On

If you have a large poset, a computer is probably useful. The wikipedia entry Hasse diagram gives two interesting references:

[1] Di Battista, G.; Tamassia, R. (1988), Algorithms for plane representation of acyclic digraphs, Theoretical Computer Science 61 (2–3): 175–178.

[2] Freese, Ralph (2004), Automated lattice drawing, Concept Lattices, LNCS 2961, Springer-Verlag, 589–590.