This paper studies t-interleaving on two-dimensional tori. Interleaving has applications in distributed data storage and burst error correction, and is closely related to Lee metric codes. A t-interleaving of a graph is defined as a vertex coloring in which any connected subgraph of t or fewer vertices has a distinct color at every vertex. We say that a torus can be perfectly t-interleaved if its t-interleaving number (the minimum number of colors needed for a t-interleaving) meets the sphere-packing lower bound, [t 2 /2]. We show that a torus is perfectly t-interleavable if and only if its dimensions are both multiples of t 2+1/2 (if t is odd) or t (if t is even). The next natural question is how much bigger the t-interleaving number is for those tori that are not perfectly t-interleavable, and the most important contribution of this paper is to find an optimal interleaving for all sufficiently large tori, proving that when a torus is large enough in both dimensions, its t-interleaving number is at most just one more than the sphere-packing lower bound. We also obtain bounds on t-interleaving numbers for the cases where one or both dimensions are not large, thus completing a general characterization of t-interleaving numbers for two-dimensional tori. Each of our upper bounds is accompanied by an efficient t-interleaving scheme that constructively achieves the bound. 2006 Society for Industrial and Applied Mathematics.
