Let G be a directed acyclic graph (DAG). 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 paper it is proved that every DAG with n vertices admits an upward (d+1, 2⌈logd n⌉−1)-topological book embedding, where d is any integer such that d ≥ 2. 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].
Upward Topological Book Embeddings of DAGs
DI GIACOMO, Emilio;GIORDANO, FRANCESCO;LIOTTA, Giuseppe
2011
Abstract
Let G be a directed acyclic graph (DAG). 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 paper it is proved that every DAG with n vertices admits an upward (d+1, 2⌈logd n⌉−1)-topological book embedding, where d is any integer such that d ≥ 2. 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].File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
