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?
$\endgroup$2 Answers
$\begingroup$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.
$\endgroup$ $\begingroup$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.
$\endgroup$
