Embedding de Bruijn and Shuffle-Exchange Graphs in Five Pages

1993/11/01 by Bojana Obrenić · 1 citation
Computer Science · Engineering · Mathematics · #Coding theory and cryptography #graph theory and CDMA systems #Algorithms and Data Compression #De Bruijn sequence #Mathematics #Embedding #Combinatorics #De Bruijn graph #Discrete mathematics #Computer science #Artificial intelligence

paper · doi:10.1137/0406049

openalex publication_date 1993/11/01 · openalex created_date 2025/10/10 · openalex updated_date 2025/11/06

Abstract

Algorithms for embedding de Bruijn and shuffle-exchange graphs in books of five pages, with cumulative pagewidth ( 5/3 )2ⁿ - ( 2/3 ) - ( 8/3 ) ( n\bmod 2 ) and ( 5/6 )2ⁿ + ( 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.

Citations

• Embedding Graphs in Books: A Layout Problem with Applications to VLSI Design
• Genus g Graphs Have Pagenumber O(√g)
• Graphs with E Edges Have Pagenumber O(√E)
• Laying Out Graphs Using Queues
• The book thickness of a graph
• Embedding Outerplanar Graphs in Small Books
• A trade-off between page number and page width of book embeddings of graphs
• The Complexity of Coloring Circular Arcs and Chords
• Embedding planar graphs in four pages

Cited by

• Book embedding [wikipedia]