[1]}
Let b̏e a class of graphs. h̏as bounded expansion if
there exists a function \(\Gamma _{: \mathbb {N}\rightarrow \mathbb {R} such that for eachgraph \textbf {G} \in  its transitive fraternal augmentation\vec{\textbf {\textbf {G} }} _0 \subseteq \vec{\textbf {\textbf {G} }} _{1} \subseteq \vec{\textbf {\textbf {G} }} _2 \subseteq \ldots  of \textbf {G}  is such that for each i \ge 0 we have\Delta ^{-}(\vec{\textbf {\textbf {G} }} _{i}) \le \Gamma _{(i) .}}Consider for instance a graph of degree \) d\(. Notice that the \) 1\(-transitivefraternal augmentation introduces an edge between nodes that were atdistance at most 2 in the initial graph. Hence, when starting with a graph ofdegree \) d\(, we end up with a graph of degree at most \) d2\(. This observationshows that the class of graphs of degree \) d\( has bounded expansion aswitnessed by the function \) (i)=d2i\(. Exhibiting the function \)\(for the other examples of classes with bounded expansion mentioned in the introduction:bounded treewidth, planar graphs, graphs excluding at least one minor, requires morework~\cite {NesetrilMendez08}.\) The following lemma shows that within a class ȍf bounded expansion the
\(i\) -th augmentation of \(\textbf {G} \in  can be computed in linear time, thelinear factor depending on \) i\( and on \) .
