Arboricity
The arboricity of an undirected graph is the minimum number of forests into which its edges can be partitioned.
Equivalently it is the minimum number of spanning forests needed to cover all the edges of the graph.
The Nash-Williams theorem provides necessary and sufficient conditions for when a graph is k-arboric.
The figure shows the complete bipartite graph K4,4, with the colors indicating a partition of its edges into three forests.
Nash-Williams proved that these two facts can be combined to characterize arboricity: if we let nS and mS denote the number of vertices and edges, respectively, of any subgraph S of the given graph, then the arboricity of the graph equals
edges, from which it follows by Nash-Williams' formula that planar graphs have arboricity at most three.
Schnyder used a special decomposition of a planar graph into three forests called a Schnyder wood to find a straight-line embedding of any planar graph into a grid of small area.
The arboricity of a graph can be expressed as a special case of a more general matroid partitioning problem,[1] in which one wishes to express a set of elements of a matroid as a union of a small number of independent sets.
As a consequence, the arboricity can be calculated by a polynomial-time algorithm (Gabow & Westermann 1992).
The current best exact algorithm computes the arboricity in
Approximations to the arboricity of a graph can be computed faster.
The star arboricity of a graph is the size of the minimum forest, each tree of which is a star (tree with at most one non-leaf node), into which the edges of the graph can be partitioned.
If a tree is not a star itself, its star arboricity is two, as can be seen by partitioning the edges into two subsets at odd and even distances from the tree root respectively.
The linear arboricity of a graph is the minimum number of linear forests (a collection of paths) into which the edges of the graph can be partitioned.
The linear arboricity of a graph is closely related to its maximum degree and its slope number.
The pseudoarboricity of a graph is the minimum number of pseudoforests into which its edges can be partitioned.
Equivalently, it is the maximum ratio of edges to vertices in any subgraph of the graph, rounded up to an integer.
As with the arboricity, the pseudoarboricity has a matroid structure allowing it to be computed efficiently (Gabow & Westermann 1992).
The thickness of a graph is the minimum number of planar subgraphs into which its edges can be partitioned.
The strength of a graph is a fractional value whose integer part gives the maximum number of disjoint spanning trees that can be drawn in a graph.
