Embedding iterated line digraphs in books
Toru Hasunuma · Networks · 2002
Abstract In this paper, we present an upper bound on the pagenumber of an iterated line digraph Lk(G) of a digraph G. Our bound depends only on the digraph G and is independent of the number of iterations k. In particular, it is proved that the pagenumber of Lk(G) does not increase with the number of iterations k. This result generalizes previous results on book‐embeddings of some particular families of iterated line digraphs such as de Bruijn digraphs, Kautz digraphs, and butterfly networks. Also, we apply our result to wrapped butterfly networks. © 2002 Wiley Periodicals, Inc.