Abstract: Spanners, Weak Spanners, and Power Spanners for Wireless Networks

Christian Schindelhauer, Klaus Volbert, and Martin Ziegler.

For $c\in\REAL$, a $c$-\emph{spanner} is a subgraph of a complete Euclidean graph satisfying that between any two vertices there exists a path of weighted length at most $c$ times their geometric distance. Based on this property to approximate a complete weighted graph, sparse spanners have found many applications, e.g., in FPTAS, geometric searching, and radio networks. In a \emph{weak} $c$-spanner, this path may be arbitrary long but must remain within a disk of radius $c$-times the Euclidean distance between the vertices. Finally in a $c$-\emph{power} spanner, the total energy consumed on such a path, where the energy is given by the sum of the \emph{squares} of the edge lengths on this path, must be at most $c$-times the square of the geometric distance of the direct 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 fails: There exists a family of $c_1$-power spanners that are no weak $C$-spanners and also a family of weak $c_2$-spanners that are no $C$-spanners for any fixed $C$ (and thus no uniform spanners, either). However the deepest result of the present work reveals that any weak spanner \emph{is} also a uniform power spanner. We further generalize the latter notion by considering $(c,\delta)$-power spanners where the sum of the $\delta$-th powers of the lengths has to be bounded; so $(\cdot,2)$-power spanners coincide with the usual power spanners and $(\cdot,1)$-power spanners are classical spanners. Interestingly, these $(\cdot,\delta)$-power spanners form a strict hierarchy where the above results still hold for {any} $\delta\geq2$; some even hold for $\delta>1$ while counterexamples exist for $\delta<2$. We show that every self-similar curve of fractal dimension $d>\delta$ is no $(C,\delta)$-power spanner for any fixed $C$, in general.