Meaning of acyclic digraph | Babel Free

Definitions

A directed acyclic graph, a finite directed graph that contains no directed cycles.

Examples

“1993, Suh-Ryung-Kim, The Competition Number and Its Variants, J. Gimbel, J.W. Kennedy, L.V. Quintas (editors), Quo Vadis, Graph Theory?: A Source Book for Challenges and Directions, Elsevier (North-Holland), page 313, In the study of the competition graph of an acyclic digraph, there are two fundamental questions which were proposed by Roberts in 1978: One is to characterize the acyclic digraphs that have interval competition graphs and the other is to characterize the graphs which are competition graphs of acyclic digraphs.”

“2009, Tamara Mchedlidze, Antonios Symvonis, Crossing-Optimal Acyclic HP-Completion for Outerplanar st-Digraphs, Hung Q. Ngo (editor), Computing and Combinatorics: 15th Annual International Conference, Proceedings, Springer, LNCS 5609, page 76, Determining whether a graph has a hamiltonian path or circuit is NP-complete [3]. The problem remains NP-complete for cubic planar graphs [3], for maximal planar graphs [9], and for planar digraphs [3]. It can be trivially solved in polynomial time for planar acyclic digraphs.”

“2018, Gregory Gutin, 3. Acyclic Digraphs, Jørgen Bang-Jensen, Gregory Gutin, Classes of Directed Graphs, Springer, page 125, Acyclic digraphs form a well-studied family of digraphs of great interest in graph theory, algorithms and applications.”

CEFR level