On peut toujours trouver un sous-graphe couvrant d’un graphe orienté acyclique qui soit un arbre (resp. une forêt).
Dans un graphe orienté acyclique, la relation d'accessibilité R(u, v) définie par «il existe un chemin de u à v» est une relation d'ordre partielle. L'algorithme du tri topologique permet de numéroter les sommets d'un graphe orienté acyclique de manière compatible avec cet ordre (autrement dit, s'il existe un chemin de u à v dans le graphe, alors le numéro de u est inférieur à celui de v).
Cette numérotation facilite la représentation par niveaux. Pour le graphe orienté acyclique ci-dessus, les sommets (7, 5, 3) forment le niveau 1, (11, 8) formant le niveau 2, (2, 9, 10) le niveau 3. Un arc de 8 vers 11 introduirait 4 niveaux, imposés par le chemin (3, 8, 11, 2).
Il est possible de trouver une couverture par chemins minimale en temps polynomial, alors que c'est un problème NP-complet dans un graphe orienté quelconque.[réf.nécessaire]
Étant donné un graphe orienté, on peut toujours enlever un certain nombre de sommets pour le transformer en graphe acyclique. Un tel ensemble est appelé coupe-cycles de sommets (feedback vertex set). Le problème algorithmique associé consiste à trouver un tel ensemble de cardinal minimum.
La notion formalise un outil traditionnel d’analyse, dont on trouve des exemples:
en matière d'ordonnancement de projet, d'organigrammes…
La technologie IOTA de transactions sécurisées a pour structure de donnée sous-jacente un graphe orienté acyclique contrairement à la blockchain plus classique qui a pour structure de donnée sous-jacente un arbre enraciné (les «chaînes» sont les chemins de la racine aux feuilles). Chaque transaction est un nœud du graphe.
