Summary: We investigate the relations between spanners, weak spanners, and power spanners in \(\mathbb R^{\mathcal D}\) for any dimension \(\mathcal D\) and apply our results to topology control in wireless networks. For \(c \in \mathbb R\), a \(c\)-spanner is a subgraph of the complete Euclidean graph satisfying the condition that between any two vertices there exists a path of length at most \(c\)-times their Euclidean distance. Based on this ability to approximate the complete Euclidean graph, sparse spanners have found many applications, e.g., in FPTAS, geometric searching, and radio networks. In a weak \(c\)-spanner, this path may be arbitrarily long, but must remain within a disk or sphere of radius \(c\)-times the Euclidean distance between the vertices. Finally in a \(c\)-power spanner, the total energy consumed on such a path, where the energy is given by the sum of the squares of the edge lengths on this path, must be at most \(c\)-times the square of the Euclidean distance of the direct edge or communication link.
While it is known that any \(c\)-spanner is also both a weak \(C_1\)-spanner and a \(C_2\)-power spanner for appropriate \(C_1\), \(C_2\) depending only on \(c\) but not on the graph under consideration, we show that the converse is not true: there exists a family of \(c_1\)-power spanners that are not weak \(C\)-spanners and also a family of weak \(c_2\)-spanners that are not \(C\)-spanners for any fixed \(C\). However a main result of this paper reveals that any weak \(c\)-spanner is also a \(C\)-power spanner for an appropriate constant \(C\).
We further generalize the latter notion by considering \((c,\sigma)\)-power spanners where the sum of the \(\sigma\)th powers of the lengths has to be bounded; so \((c,2)\)-power spanners coincide with the usual power spanners and \((c,1)\)-power spanners are classical spanners. Interestingly, these \((c,\sigma)\)-power spanners form a strict hierarchy where the above results still hold for any \(\sigma \geq \mathcal D\) some even hold for \(\sigma >1\) while counter-examples exist for \(\delta < \mathcal D\). We show that every self-similar curve of fractal dimension \(\mathcal D_f > \delta\) is not a \((C,\delta)\)-power spanner for any fixed \(C\), in general.
Finally, we consider the sparsified Yao-graph (SparsY-graph or YY) that is a well-known sparse topology for wireless networks. We prove that all SparsY-graphs are weak \(c\)-spanners for a constant \(c\) and hence they allow us to approximate energy-optimal wireless networks by a constant factor.