Orders with level diagrams (Q2640624)

For elements a and b in an ordered set P, a is called an upper cover of b and b a lower cover of a if \(a>b\) and, for each x in P, \(a>x\geq b\) implies \(x=b\). The ordered set P is called upper levelled (lower levelled) if there is a diagram of P such that all upper covers (lower covers) are on a horizontal level. It is proved that the following statements are equivalent: (a) P is upper levelled. (b) P is lower levelled. (c) P contains no alternating cover cycle, i.e. a subset \(\{x_ 1,a_ 1,a_ 2,...,a_ n,c_ 1,c_ 2,...,c_ n\},\) \(n\geq 2\), where \(c_ i\) covers \(a_ i\), for \(i\leq n\), \(c_{i+1}>a_ i\), for \(i\leq n-1\), \(c_ 1>x>a_ n\) are the only comparabilities. Finally efficient algorithms are described, both to check whether an ordered set has a given level-type property and, if it does, to draw a corresponding diagram.