Multilayer Grid Embeddings of Iterated Line Digraphs.
Toru Hasunuma · Computing: The Australasian Theory Symposium · 2006
In this paper, we show that for any fixed d-regular digraph G, every iterated line digraph Lk(G) (k ≥ 1) can be embedded in d layers using O(n2) area, where n is the number of vertices in Lk(G). Also, we present [EQUATION] lower bound on the area of Lk(G) for any fixed number of layers. Besides, we apply the results to specific families of iterated line digraphs such as de Bruijn digraphs, Kautz digraphs, and wrapped butterfly digraphs.