Bow-tie decomposition in directed graphs

The bow-tie structure is frequently cited in the literature of the World Wide Web and in many other areas, such as metabolic networks, but it has never been precisely defined, so that to some extent the concept being discussed remains vague. This paper first provides a formal definition of a bow-tie structure relative to a given strongly connected components. That definition details distinctions which are not usually made, such as the difference between intendrils and outtendrils. Theorems and algorithms are then provided to justify and support the definition. Finally a bow-tie decomposition algorithm is developed and illustrated. The algorithms have also been implemented and tested on a university domain.