The pagenumber of ordered sets.

Abstract

The main result is this The pagenumber of a series-parallel planar ordered set is at most two. We present an $O(n\sp3)$ algorithm to construct a two-page embedding in the case that it is a lattice, where n is the number of the elements of the lattice. Once consequence of independent interest, is a characterization of series-parallel planar ordered sets. A k-edge set $\{(a\sb{i}, b\sb{i}):1\le i\le k\},$ in an ordered set P, forms a k-twist in a linear extension L of P, if we have in ?? We give necessary and sufficient conditions for the existence of a linear extension L of an ordered set P such that k edges form a k-twist in L. We also, give lower and upper bounds in some classes of ordered sets. We proved that the problem to determine minimum number of pages required for a fixed linear extension of an ordered set is NP-complete. We conjecture that the pagenumber of planar ordered sets is unbounded. In contrast, we conjecture that the pagenumber of planar lattices is at most four.