  In 1999, Brodal and Fagerberg (BF) gave an algorithm for maintaining a low
outdegree orientation of a dynamic uniformly sparse graph. Specifically, for a
dynamic graph on $n$-vertices, with arboricity bounded by $\alpha$ at all
times, the BF algorithm supports edge updates in $O(\log n)$ amortized update
time, while keeping the maximum outdegree in the graph bounded by $O(\alpha)$.
Such an orientation provides a basic data structure for uniformly sparse
graphs, which found applications to a plethora of dynamic graph algorithms.
  A significant weakness of the BF algorithm is the possible \emph{temporary}
blowup of the maximum outdegree, following edge insertions. Although BF
eventually reduces all outdegrees to $O(\alpha)$, local memory usage at the
vertices, which is an important quality measure in distributed systems, cannot
be bounded. We show how to modify the BF algorithm to guarantee that the
outdegrees of all vertices are bounded by $O(\alpha)$ at all times, without
hurting any of its other properties, and present an efficient distributed
implementation of the modified algorithm. This provides the \emph{first}
representation of distributed networks in which the local memory usage at all
vertices is bounded by the arboricity (which is essentially the average degree
of the densest subgraph) rather than the maximum degree.
  For settings where there are no local memory constraints, we take the
temporary outdegree blowup to the extreme and allow a permanent outdegree
blowup. This allows us to address the second significant weakness of the BF
algorithm -- its inherently \emph{global} nature: An insertion of an edge
$(u,v)$ may trigger changes in the orientations of edges that are far away from
$u$ and $v$. We suggest an alternative \emph{local} scheme, which does not
guarantee any outdegree bound on the vertices, yet is just as efficient as the
BF scheme for various applications.
