Hasse Diagram - Upward Planarity

Upward Planarity

If a partial order can be drawn as a Hasse diagram in which no two edges cross, its covering graph is said to be upward planar. A number of results on upward planarity and on crossing-free Hasse diagram construction are known:

• If the partial order to be drawn is a lattice, then it can be drawn without crossings if and only if it has order dimension at most two. In this case, a non-crossing drawing may be found by deriving Cartesian coordinates for the elements from their positions in the two linear orders realizing the order dimension, and then rotating the drawing counterclockwise by a 45-degree angle.
• If the partial order has at most one minimal element, or it has at most one maximal element, then it may be tested in linear time whether it has a non-crossing Hasse diagram.
• It is NP-complete to determine whether a partial order with multiple sources and sinks can be drawn as a crossing-free Hasse diagram. However, finding a crossing-free Hasse diagram is fixed-parameter tractable when parametrized by the number of articulation points and triconnected components of the transitive reduction of the partial order.
• If the y-coordinates of the elements of a partial order are specified, then a crossing-free Hasse diagram respecting those coordinate assignments can be found in linear time, if such a diagram exists. In particular, if the input poset is a graded poset, it is possible to determine in linear time whether there is a crossing-free Hasse diagram in which the height of each vertex is proportional to its rank.