  We investigate decompositions of a graph into a small number of low diameter
subgraphs. Let P(n,\epsilon,d) be the smallest k such that every graph G=(V,E)
on n vertices has an edge partition E=E_0 \cup E_1 \cup ... \cup E_k such that
|E_0| \leq \epsilon n^2 and for all 1 \leq i \leq k the diameter of the
subgraph spanned by E_i is at most d. Using Szemer\'edi's regularity lemma,
Polcyn and Ruci\'nski showed that P(n,\epsilon,4) is bounded above by a
constant depending only \epsilon. This shows that every dense graph can be
partitioned into a small number of ``small worlds'' provided that few edges can
be ignored. Improving on their result, we determine P(n,\epsilon,d) within an
absolute constant factor, showing that P(n,\epsilon,2) = \Theta(n) is unbounded
for \epsilon < 1/4, P(n,\epsilon,3) = \Theta(1/\epsilon^2) for \epsilon >
n^{-1/2} and P(n,\epsilon,4) = \Theta(1/\epsilon) for \epsilon > n^{-1}. We
also prove that if G has large minimum degree, all the edges of G can be
covered by a small number of low diameter subgraphs. Finally, we extend some of
these results to hypergraphs, improving earlier work of Polcyn, R\"odl,
Ruci\'nski, and Szemer\'edi.
