On embedding 2-dimensional toroidal grids into de Bruijn graphs with clocked congestion one

For integers m,d,D with m ge 3, d ge 2, and D ge 2, let T (m) be a 2--dimensional quadratic toroidal grid with side length m and let B (d,D) be the base d, dimension D de Bruijn graph; assume that |T ( m ) | = | B (d,D ) |. The starting point for our inves-ti-ga-tions is the observation that, for m, D even, embeddings f : T (m) rightarrow B (d,D) with load 1, expansion 1, and dilation D/2 can easily be found (and have previously been described in the literature). In the present paper, we pose the question whether or not there exist embeddings f:T (m) rightarrow B (d,D) with these properties em and with clocked congestion 1. We prove results implying a positive answer to this question when d is greater than two. For d=2, we do not have a complete answer, but present partial results.