On the Book Embedding of Ordered Sets

Abstract

In the book embedding of an ordered set, the elements of the set are embedded along the spine of a book to form a linear extension. The pagenumber (or stack number) is the minimum number of pages needed to draw the edges as simple curves such that
edges drawn on the same page do not intersect. The pagenumber problem for ordered sets is known to be NP-complete, even if the order of the elements on the spine is-fixed. In this paper, we investigate this problem for some classes of ordered sets. We provide an efficient algorithm for embedding bipartite interval orders in a book with the minimum number of pages. We also give an upper bound for the pagenumber of general bipartite ordered sets and the pagenumber of complete multipartite ordered sets. At the end of this paper we discuss the effect of a number of diagram operations on the pagenumber of ordered sets. We give an answer to an open question by Nowakowski and Parker $[7]$ and we provide several known and new open questions we consider worth investigating.