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 toR (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 and Xu, 2012; Bouabdallah and Sotteau, 1993; Fernandez de la Vega and Gordone, 1992; de la Vega and Manoussakis, 1992). 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.