Edge-disjoint spanners in tori

A spanning subgraph S=(V,E′)S=(V,E′) of a connected graph G=(V,E)G=(V,E) is an (x+c)(x+c)-spanner if for any pair of vertices uu and vv, dS(u,v)≤dG(u,v)+cdS(u,v)≤dG(u,v)+c where dGdG and dSdS are the usual distance functions in GG and SS, respectively. The parameter cc is called the delay of the spanner. We study edge-disjoint spanners in graphs in multi-dimensional tori. We show that each two-dimensional torus has a set of two edge-disjoint spanners of delay approximately the size of the smaller dimension. Moreover, we show that this delay is close to the best possible. In three-dimensional tori, we find a set of three edge-disjoint spanners with delay approximately the sum of the sizes of the two smaller dimensions when all dimensions are of even size. Surprisingly, we also find a set of two edge-disjoint spanners in three-dimensional tori of constant delay. In dd-dimensional tori, we show that for any k≤d/5k≤d/5, there is a set of kk edge-disjoint spanners with delay depending only on kk and the size of the smaller kk dimensions.