Upward Topological Book Embeddings of DAGs

Let G be a directed acyclic graph. An upward (k, h)-topological book embedding of G is an upward book embedding on k pages of a subdivision of G where every edge is replaced by a path having at most h+2 vertices. In this extended abstract it is shown that every DAG with n vertices admits an upward (d +1, 2\lceil log_d \rceil n - 1)-topological book embedding, where d is any integer such that d \geq 2. The result extends to the upward case well-known theorems for topological book embeddings of undirected graphs.