Embedding de Bruijn and Shuffle-Exchange Graphs in Five Pages
Bojana Obrenić · SIAM Journal on Discrete Mathematics · 1993
Algorithms for embedding de Bruijn and shuffle-exchange graphs in books of five pages, with cumulative pagewidth $( 5/3 )2^n - ( 2/3 ) - ( 8/3 ) ( n\bmod 2 )$ and $( 5/6 )2^n + ( 2/3 ) - ( 4/3 ) ( n\bmod 2 )$, respectively, are presented. These are the first nontrivial bounds on the pagenumber of de Bruijn and shuffle-exchange graphs.