Arboricity
Encyclopedia
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 figure shows the complete bipartite graph
K4,4, with the colors indicating a partition of its edges into three forests. K4,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 K4,4 is three.
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
. 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 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
Any planar graph
with
vertices has at most 
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.
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 .
(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. Therefore, the star arboricity of any graph is at least equal to the arboricity, and at most equal to twice the arboricity.
The linear arboricity of a graph is the size of the minimum linear forest (a forest in which all vertices are incident to at most two edges) into which the edges of the graph can be partitioned. The linear arboricity of a graph is closely related to its maximum degree
.
The pseudoarboricity of a graph is the minimum number of pseudoforest
s into which its edges can be partitioned. Equivalently, it is the maximum ratio of edges to vertices in any subgraph of the graph. As with the arboricity, the pseudoarboricity has a matroid structure allowing it to be computed efficiently .
The thickness
of a graph is the minimum number of planar subgraphs into which its edges can be partitioned. As any planar graph has arboricity three, the thickness of any graph is at least equal to a third of the arboricity, and at most equal to the arboricity.
The degeneracy
of a graph is the maximum, over all induced subgraphs of the graph, of the minimum degree
of a vertex in the subgraph. The degeneracy of a graph with arboricity
is at least equal to 
, and at most equal to 
. The coloring number of a graph, also known as its Szekeres-Wilf number is always equal to its degeneracy plus 1 .
Tree (graph theory)
In mathematics, more specifically graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one simple path. In other words, any connected graph without cycles is a tree...
into which its edges can be partitioned
Partition of a set
In mathematics, a partition of a set X is a division of X into non-overlapping and non-empty "parts" or "blocks" or "cells" that cover all of X...
. Equivalently it is the minimum number of spanning forests
Spanning tree (mathematics)
In the mathematical field of graph theory, a spanning tree T of a connected, undirected graph G is a tree composed of all the vertices and some of the edges of G. Informally, a spanning tree of G is a selection of edges of G that form a tree spanning every vertex...
needed to cover all the edges of the graph.
Example
Complete bipartite graph
In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set.- Definition :...
K4,4, with the colors indicating a partition of its edges into three forests. K4,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 K4,4 is three.
Arboricity as a measure of density
The arboricity of a graph is a measure of how denseDense graph
In mathematics, a dense graph is a graph in which the number of edges is close to the maximal number of edges. The opposite, a graph with only a few edges, is a sparse graph...
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
. 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-WilliamsCrispin St. J. A. Nash-Williams
Crispin St. John Alvah Nash-Williams was a British and Canadian mathematician. His research interest was in the field of discrete mathematics, especially graph theory....
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
Any planar graph
Planar graph
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints...
with
vertices has at most 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 embeddingFáry's theorem
In mathematics, Fáry's theorem states that any simple planar graph can be drawn without crossings so that its edges are straight line segments. That is, the ability to draw graph edges as curves instead of as straight line segments does not allow a larger class of graphs to be drawn...
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 sumMatroid
In combinatorics, a branch of mathematics, a matroid or independence structure is a structure that captures the essence of a notion of "independence" that generalizes linear independence in vector spaces....
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 .
Related concepts
The star arboricity of a graph is the size of the minimum forest, each tree of which is a starStar (graph theory)
In graph theory, a star Sk is the complete bipartite graph K1,k: a tree with one internal node and k leaves...
(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. Therefore, the star arboricity of any graph is at least equal to the arboricity, and at most equal to twice the arboricity.
The linear arboricity of a graph is the size of the minimum linear forest (a forest in which all vertices are incident to at most two edges) into which the edges of the graph can be partitioned. The linear arboricity of a graph is closely related to its maximum degree
Degree (graph theory)
In graph theory, the degree of a vertex of a graph is the number of edges incident to the vertex, with loops counted twice. The degree of a vertex v is denoted \deg. The maximum degree of a graph G, denoted by Δ, and the minimum degree of a graph, denoted by δ, are the maximum and minimum degree...
.
The pseudoarboricity of a graph is the minimum number of pseudoforest
Pseudoforest
In graph theory, a pseudoforest is an undirected graph in which every connected component has at most one cycle. That is, it is a system of vertices and edges connecting pairs of vertices, such that no two cycles of consecutive edges share any vertex with each other, nor can any two cycles be...
s into which its edges can be partitioned. Equivalently, it is the maximum ratio of edges to vertices in any subgraph of the graph. As with the arboricity, the pseudoarboricity has a matroid structure allowing it to be computed efficiently .
The thickness
Thickness
Thickness may refer to:Thickness may refer to:* Thickness in graph theory* Thickness of layers in Geology* Thickness The difference in height between two atmospheric pressure levels* Thickness planer a woodworking machine...
of a graph is the minimum number of planar subgraphs into which its edges can be partitioned. As any planar graph has arboricity three, the thickness of any graph is at least equal to a third of the arboricity, and at most equal to the arboricity.
The degeneracy
Degeneracy (graph theory)
In graph theory, a k-degenerate graph is an undirected graph in which every subgraph has a vertex of degree at most k: that is, some vertex in the subgraph touches k or fewer of the subgraph's edges. The degeneracy of a graph is the smallest value of k for which it is k-degenerate...
of a graph is the maximum, over all induced subgraphs of the graph, of the minimum degree
Degree (graph theory)
In graph theory, the degree of a vertex of a graph is the number of edges incident to the vertex, with loops counted twice. The degree of a vertex v is denoted \deg. The maximum degree of a graph G, denoted by Δ, and the minimum degree of a graph, denoted by δ, are the maximum and minimum degree...
of a vertex in the subgraph. The degeneracy of a graph with arboricity
is at least equal to , and at most equal to . The coloring number of a graph, also known as its Szekeres-Wilf number is always equal to its degeneracy plus 1 .