Abstract: Symmetric disk graphs are often used to model wireless
communication networks. Given a set S of n points in R^d (representing
n transceivers) and a transmission range assignment r: S -> R,
the symmetric disk graph of S is the undirected graph over S whose set of edges
is E = {(u,v) |  r(u) \ge |uv| and r(v) \ge |uv|}, where |uv| denotes
the distance between points u and v.
We prove that the weight of the minimum spanning tree of any
connected symmetric disk graph over a set S of points is
only O(log n) times the weight of the minimum spanning tree of
the complete Euclidean graph over S.

We also present several applications of this somewhat surprising theorem,
including a result concerning range assignment in wireless networks,
and an alternative and simpler proof of the w-gap theorem.

Finally, we show that in the non-symmetric model (where
E = {(u,v) | r(u) \ge |uv|}) the weight of a minimum spanning subgraph
might be as big as O(n) times the weight of the minimum spanning tree of
the complete Euclidean graph over S.