Circuit rank

[1] It is possible to construct a minimum-size set of edges that breaks all cycles efficiently, either using a greedy algorithm or by complementing a spanning forest.

It counts the ears in an ear decomposition of the graph, forms the basis of parameterized complexity on almost-trees, and has been applied in software metrics as part of the definition of cyclomatic complexity of a piece of code.

Alternatively, a minimum set of edges that breaks all cycles can be found by constructing a spanning forest of G and choosing the complementary set of edges that do not belong to the spanning forest.

In algebraic graph theory, the circuit rank is also the dimension of the cycle space of

[1] This count of independent cycles can also be explained using homology theory, a branch of topology.

Any graph G may be viewed as an example of a 1-dimensional simplicial complex, a type of topological space formed by representing each graph edge by a line segment and gluing these line segments together at their endpoints.

A variant of the circuit rank for planar graphs, normalized by dividing by the maximum possible circuit rank of any planar graph with the same vertex set, is called the meshedness coefficient.

For a connected planar graph with m edges and n vertices, the meshedness coefficient can be computed by the formula[7] Here, the numerator

is also called a r-almost-tree, because only r edges need to be removed from the graph to make it into a tree or forest.

Both cycle rank and the minimum feedback arc set are NP-hard to compute.

This principle forms the basis of the definition of cyclomatic complexity, a software metric for estimating how complicated a piece of computer code is.

This graph has circuit rank r = 2 because it can be made into a tree by removing two edges, for instance the edges 1–2 and 2–3, but removing any one edge leaves a cycle in the graph.