  The arboricity $\Gamma$ of a graph is the minimum number of forests its edge
set can be partitioned into. Previous approximation schemes were
nonconstructive, i.e., they only approximated the arboricity as a value without
computing a corresponding forest partition. This is because they operate on the
related pseudoforest partitions or the dual problem of finding dense subgraphs.
  We propose an algorithm for converting a partition of $k$ pseudoforests into
a partition of $k+1$ forests in $O(mk\log k + m \log n)$ time with a data
structure by Brodal and Fagerberg that stores graphs of arboricity $k$. A
slightly better bound can be given when perfect hashing is used. When applied
to a pseudoforest partition obtained from Kowalik's approximation scheme, our
conversion implies a constructive $(1+\epsilon)$-approximation algorithm with
runtime $O(m \log n \log \Gamma\, \epsilon^{-1})$ for every $\epsilon > 0$. For
fixed $\epsilon$, the runtime can be reduced to $O(m \log n)$.
  Our conversion also implies a near-exact algorithm that computes a partition
into at most $\Gamma+2$ forests in $O(m\log n \,\Gamma \log^* \Gamma)$ time. It
might also pave the way to faster exact arboricity algorithms.
  We also make several remarks on approximation algorithms for the
pseudoarboricity and the equivalent graph orientations with smallest maximum
indegree, and correct some mistakes made in the literature.

Data Structures and Algorithms