Ordered sets, pagenumbers and planarity (Q913833)

Given a digraph G, a book embedding is an embedding of the vertices and edges of G, with the vertices embedded along the spine (i.e., in a line fashion) and the edges on the pages so that each edge lies on only one page and so that no edges cross. The page number of G is the minimum number of pages needed for any book embeddng of G. If P is a poset, then P has associated graphs, e.g., the covering graph, the Hasse diagram, the relation graph with directed edge for each inequality \(x<y\). Each such graph has a page number. If G is the relation graph of P, we write \(p(P,\leq)\) for \(p(G)\). Similarly \(p(cov(P))\) denotes the page number of the covering graph. Obviously, \(p(cov(P))\leq p(P,\leq)\), but the full relationship between these two invariants is not clear. The main and interesting theorem (T2) in this paper is the graph theoretical result that if cov(P) is a planar graph, i.e., if P is a planar poset, then \(e(P)\leq 2v(P)-2-2ht(P)\), where e(P) is the number of edges, v(P) is the number of vertices and ht(P) is the height of \(cov(P)\) or P. From this theorem other bounds on \(p(cov(P))\) are derived. Using an argument on convex cutsets of P (or \(cov(P))\), some upper bounds are also obtained. These are used to determine that \(p(\underline k^ n)\leq 2n-2\) (T7), where \(\underline k\) is an ordered chain with k vertices. From the point of view of scheduling, the page number is an interesting invariant if each edge represents a task to be performed and if pages represent subschedules of a particularly nice kind. The authors give some indication of this fact in their discussion and introduction.