Embedding de Bruijn, Kautz and shuffle-exchange networks in books

✍ Scribed by Toru Hasunuma; Yukio Shibata

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 839 KB
• Volume: 78
• Category: Article
• ISSN: 0166-218X
• DOI: 10.1016/s0166-218x(97)00009-7

✦ Synopsis

We show that the de Bruijn digraph B(d,D), D > 1 and the Kautz digraph K(d,D) can be embedded in (d + 1) pages with cumulative pagewidth ~dDe2(3d3 -2d2 + 4d -d(d mod 2) ~ 4) and idD-'(3d' + 4d + (d mod2)), respectively. Also we show that the shuffle-exchange graph S(D; D > 2 can be embedded in 3 pages with cumulative pagewidth 5. 20e3. From these results, the pagenumbers of B(2,D),K(2,D)

and S(D) are determined to be 3.