Average-degree Bounded Graphs are no harder than Maximum-degree Bounded Graphs (for distance oracles with purely multiplicative stretch) I'm trying to understand a specific part from an article of Agarwal and co.
It is about Distance Oracles but there is a specific explanation of How to convert from average-degree graph to maximum-degree bounded graph with linear complexity.
I can't understand it so I need a simple language explanation...
This is the link to the article: http://arxiv.org/pdf/1201.2703.pdf and the specific explanation is in section 5.
From the article: (I don't understand the reduction)

Let G = (V, E) be a connected graph with average degree ∆. Given G, we
will first create a ∆-degree bounded graph G∆ = (V∆ , E∆ ). Then, we
show how can be used on G∆ to return stretch-s paths on G.
The Reduction: For each node v ∈ V , create α v = ⌈deg(v)/∆⌉ nodes v1 , v2
, . . . , vαv in V∆ . For each edge e = (u, v) ∈ E, if deg(u) ≤ ∆ and
deg(v) ≤ ∆, create an edge e = (u1 , v1 ) in E∆ . For each node v ∈ V
, we arbitrarily distribute N (v) in G to the nodes corresponding to v
in G∆ such that for i = 1, 2, . . . , (α v − 1), |N (v) ∩ N (vi )| = ∆
and |N (v) ∩ N (vαv )| = (deg(v) − (α v − 1) · ∆). Finally, for each
pair vi , vi+1 , we create an edge in E∆ of weight 0.
In order to answer an approximate distance query for any pair of nodes u, v ∈ V , we use D to answer approximate distance queries between u1 , v1 ∈ V∆
in G∆ and let the length of the path returned by the data structure be
δ′ . We output the distance δ′ as an approximate distance for the pair
of nodes in G.

Thanks!
Here is, perhaps a more understandable, proof. Let me start with the following claim:


  Let $G=(V,E)$ be an undirected weighted graph with $n$ vertices
      and $m$ edges. For any integer $k \geq 3$, one can convert $G$
      into a graph $H$ with maximum degree $k$ with $m' = (1+2/(k-2))m$
      edges and $n' = n + 2m/(k-2)$ vertices. Furthermore, for any two
      vertices $u$ and $v$ in $G$, the distance between any copy of $u$
      to any copy of $v$ in $H$ is equal to the distance of $u$ and $v$
      in $G$. This conversion can be done in $O(n + m)$ time.


Here is a rough proof to the above claim:

We start with a copy $H$ of $G$. We scan the vertices of $H$ one by one. If a vertex $v \in V(H)$ has degree $\leq k$ then we leave it as it is. Otherwise, consider $v$ and the edges coming out of it. We replace $v$ by a list of $\lceil \deg(v)/(k-2) \rceil$ vertices,    all of them connected by a new path of edges having weight $0$.    Each of these new vertices is assigned at most $k-2$ edges that    were adjacent to $v$ (these reassigned edges keep their original
    weight).  We repeat this process till the degrees in the new graph
    are bounded by $k$.

The number of new vertices created during this process to replace a single vertex $v$ is $ \lceil \deg(v) /(k-2) \rceil$. The number of    new edges created for $v$ is $ \lceil \deg(v) /(k-2) \rceil - 1$.    Clearly, the new graph has $\sum_{v \in V(G)} \lceil \deg(v)/(k-2) \rceil \leq n + \sum_{v \in V(G)} \deg(v) /(k-2) \leq n +
    2m/(k-2)$ vertices. The number of new edges added because of $v$
    is at most $2m/(k-2)$.

In the new graph, we replace every vertex by a path (with all its
    edges having weight $0$), and kept the original edges. As such,
    the distance between two vertices in the modified graph is the
    same as the distance between the corresponding vertices in the
    original graph.

A corollary of the above claim is:


  Let $G=(V,E)$ be an undirected weighted graph with $n$ vertices,
      $m$ edges, and average degree $\mu = 2m/n$. Then one construct
      an equivalent graph with maximum degree $k = \lceil {\mu +2} \rceil$, such
      that the new graph has $2n$ vertices, $m+n$ edges, and has the
      same distances between any pair of vertices as the distance in the
      original graph between the corresponding vertices. The new graph can
      be computed in $O(n + m)$ time.


The above implies that given a graph with average degree $\mu$, we can
replace it with a graph with maximum degree $\mu + 2$, and build the
distance oracle on this new graph instead of the original graph.