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 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.

Example

K 4,4 into three forests, showing that it has arboricity at most three.]] The figure shows the complete bipartite graph K 4,4 , with the colors indicating a partition of its edges into three forests. K 4,4 cannot be partitioned into fewer forests, because any forest on its eight vertices has at most seven edges, while the overall graph has sixteen edges, more than double the number of edges in a single forest. Therefore, the arboricity of K 4,4 is three.

Arboricity as a measure of density

The arboricity of a graph is a measure of how dense the graph is: graphs with many edges have high arboricity, and graphs with high arboricity must have a dense subgraph. In more detail, as any n-vertex forest has at most n − 1 edges, the arboricity of a graph with n vertices and m edges is at least \lceil m/(n-1)\rceil . Additionally, the subgraphs of any graph cannot have arboricity larger than the graph itself, or equivalently the arboricity of a graph must be at least the maximum arboricity of any of its subgraphs. Nash-Williams proved that these two facts can be combined to characterize arboricity: if we let n S and m S denote the number of vertices and edges, respectively, of any subgraph S of the given graph, then the arboricity of the graph equals \max_S\{\lceil m_S/(n_S-1)\rceil\}. Any planar graph with n vertices has at most 3n-6 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.

Algorithms

The arboricity of a graph can be expressed as a special case of a more general matroid partitioning problem, 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 . The current best exact algorithm computes the arboricity in O(m \sqrt{m}) time, where m is the number of edges in the graph. Approximations to the arboricity of a graph can be computed faster. There are linear time 2-approximation algorithms.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1343671926 under CC BY-SA 4.0; modifications have been made.