Grid spanners with low forwarding index for energy efficient networks

A routing R of a connected graph G is a collection that contains simple paths connecting every ordered pair of vertices in G. The edge-forwarding index with respect to R (or simply the forwarding index with respect to R) π(G,R) of G is the maximum number of paths in R passing through any edge of G. The forwarding index π(G) of G is the minimum π(G,R) over all routings R's of G. This parameter has been studied for different graph classes [Xu, J.-M. and M. Xu, The forwarding indices of graphs – a survey, CoRR abs/1204.2604 (2012)], [Bouabdallah, A. and D. Sotteau, On the edge forwarding index problem for small graphs, Networks 23 (1993), pp. 249–255], [Fernandez de la Vega, W. and L. M. Gordones, The forwarding indices of random graphs, Random Structures and Algorithms 3 (1992), pp. 107–116], [de la Vega, W. F. and Y. Manoussakis, The forwarding index of communication networks with given connectivity, Discrete Appl. Math. 37–38 (1992), pp. 147–155]. Motivated by energy efficiency, we look, for different numbers of edges, at the best spanning graphs of a square grid, namely those with a low forwarding index.