Upward Topological Book Embeddings of DAGs
Emilio Di Giacomo, Francesco Giordano, Giuseppe Liotta · SIAM Journal on Discrete Mathematics · 2011
Let [Formula: see text] be a directed acyclic graph (DAG). An upward [Formula: see text]-topological book embedding of [Formula: see text] is an upward book embedding on [Formula: see text] pages of a subdivision of [Formula: see text] where every edge is replaced by a path having at most [Formula: see text] vertices. In this paper it is proved that every DAG with [Formula: see text] vertices admits an upward ([Formula: see text], [Formula: see text])-topological book embedding, where [Formula: see text] is any integer such that [Formula: see text]. The result extends to the upward case well-known theorems for topological book embeddings of undirected graphs [H. Enomoto and M. S. Miyauchi, SIAM J. Discrete Math., 12 (1999), pp. 337–341], [M. S. Miyauchi, IEICE Transactions, 88-A (2005), pp. 1136–1139].