We study the parallel complexity of computing the arboricity of a graph, defined as the minimum number of forests into which its edges can be partitioned.
For graphs of bounded treewidth, we present a simple dynamic programming–based parallel algorithm that constructs an optimal partition of the edges into forests.
For graphs of bounded genus, we give an alternative and simple parallel algorithm for computing arboricity by adapting Goldberg’s method for finding dense subgraphs.