Embedding Cartesian Products of Graphs into de Bruijn Graphs

Given a Cartesian productG=G₁× … ×G_m(m≥ 2) of nontrivial connected graphsG_iand then-dimensional baseBde Bruijn graphD=D_B(n), it is investigated whether or notGis a spanning subgraph ofD. Special attention is given to graphsG₁× … ×G_mwhich are relevant for parallel computing, namely, to Cartesian products of paths (grids) or cycles (tori). For 2-dimensional de Bruijn graphsD, we present a theorem stating that certain structural assumptions on the factorsG₁, …,G_mensure thatG₁× … ×G_mis a spanning subgraph ofD. As corollaries, we obtain results improving previous results of Heydemannet al.(J. Parallel Distrib. Comput.23 (1994), 104–111) on embedding grids and tori into de Bruijn graphs. Specifically, we obtain that (i) any gridG=G₁× … ×G_mis a spanning subgraph ofD=D_B(2) provided that |G| = |D|, and (ii) any torusG=G₁× … ×G_mis a spanning subgraph ofD=D_B(2) provided that |G| = |D| and that theG_iare cycles of even length ≥4. We show that these results have consequences for the casen> 2, too: for evenn, we apply our results to obtain embeddings of grids and toriGinto de Bruijn graphsD_B(n) with dilationn/2, where the baseBis a fixed integer ≥2, andnis big enough to ensure |G| ≤ |D_B(n)|. We also contrast our results forn= 2 with nonexistence results forn≥ 3 and briefly describe experimental results in the area of parallel image processing.