In graph theory, the cycle rank of a directed graph is a digraph connectivity measure proposed first by Eggan and Büchi . Intuitively, this concept measures how close a digraph is to a directed acyclic graph (DAG), in the sense that a DAG has cycle rank zero, while a complete digraph of order n with a self-loop at each vertex has cycle rank n. The cycle rank of a directed graph is closely related to the tree-depth of an undirected graph and to the star height of a regular language. It has also found use in sparse matrix computations (see ) and logic . Definition The cycle rank r(G) of a digraph is inductively defined as follows: If G is acyclic, then . If G is strongly connected and E is nonempty, then where is the digraph resulting from deletion of vertex and all edges beginning or ending at . If G is not strongly connected, then r(G) is equal to the maximum cycle rank among all strongly connected components of G. The tree-depth of an undirected graph has a very similar definition, using undirected connectivity and connected components in place of strong connectivity and strongly connected components. History Cycle rank was introduced by in the context of star height of regular languages. It was rediscovered by as a generalization of undirected tree-depth, which had been developed beginning in the 1980s and applied to sparse matrix computations . Examples The cycle rank of a directed acyclic graph is 0, while a complete digraph of order n with a self-loop at each vertex has cycle rank n. Apart from these, the cycle rank of a few other digraphs is known: the undirected path of order n, which possesses a symmetric edge relation and no self-loops, has cycle rank . For the directed -torus , i.e., the cartesian product of two directed circuits of lengths m and n, we have and for m ≠ n (, ). Computing the cycle rank Computing the cycle rank is computationally hard: proves that the corresponding decision problem is NP-complete, even for sparse digraphs of maximum outdegree at most 2. On the positive side, the problem is solvable in time on digraphs of maximum outdegree at most 2, and in time on general digraphs. There is an approximation algorithm with approximation ratio . Applications Star height of regular languages The first application of cycle rank was