With the help of Narsingh Deo’s book Graph Theory with Applications to Engineering and Computer Science (thank you @ShubhamJohri for the reference) I could answer to myself:
Section 9.4. Directed paths and connectedness:
Walks, paths, and circuits in a directed graph, in addition to being what they are in the corresponding undirected graph, have the added consideration of orientation. […]
A directed walk from a vertex vi to vj is an alternating sequence of vertices and edges, beginning with vi and ending with vj, such that each edge is oriented from the vertex preceding it to the vertex following it. Of course, no edge in a directed walk appears more than once, but a vertex may appear more than once, just as in the case of undirected graphs. A semiwalk in a directed graph is a walk in the corresponding undirected graph, but is not a directed walk. A walk in a digraph can mean either a directed walk or a semiwalk.
The definitions of circuit, semicircuit, and directed circuit can be written similarly. […]
Connected Digraphs: In Chapter 2 a graph (i.e., undirected graph) was defined as connected if there was at least one path between every pair of vertices. In a digraph, there are two different types of paths. Consequently, we have two different types of connectedness in digraphs. A digraph G is said to be strongly connected if there it at least one directed path from every vertex to every other vertex. A digraph G is said to be weakly connected if its corresponding undirected graph is connected but G is not strongly connected. […] The statement that a digraph G is connected simply means that its corresponding undirected graph is connected; and thus G may be strongly or weakly connected. A directed graph that is not connected is dubbed as disconnected.
Section 9.6. Trees with directed edges:
A tree (for undirected graphs) was defined as a connected graph without any circuit. The basic concept as well as the term “tree” remains the same for digraphs. A tree is a connected digraph that has no circuit—neither a directed circuit nor a semicircuit. A tree of n vertices contains n − 1 directed edges and has properties similar to those with undirected edges. […]
Arborescence: A digraph G is said to be an arborescence if
G contains no circuit—neither directed nor semicircuit.
In G there is precisely one vertex v of zero in-degree.
This vertex v is called the root of the arborescence. […]
THEOREM 9.2. An arborescence is a tree in which every vertex other than the root has an in-degree of exactly one.
[…]
An arborescence is in a sense a tree directed out of the root. Therefore an arborescence is sometimes referred to as an out-tree. (Reversing the direction of every edge in an arborescence will produce what may be called an in-tree.)
Section 9.11. Acyclic digraphs and decyclization:
In many situations semicircuits are of no significance, and one is concerned only with whether or not a given digraph has a directed circuit. A digraph that has no directed circuit is called acyclic.
To sum up, for directed graphs:
- a connected directed graph is either a strongly connected directed graph or a weakly connected directed graph;
- a cycle is either a directed cycle or a semicycle;
- an acyclic directed graph (DAG) is a directed graph without directed cycles;
- a directed tree is a connected directed graph without cycles (not to be confused with a connected directed graph without directed cycles—a connected DAG). In other words, it is a directed graph whose underlying graph is a tree;
- an arborescence (or out-tree) is a directed tree whose vertices have a maximum in-degree of 1;
- an anti-arborescence (or in-tree) is a directed tree whose vertices have a maximum out-degree of 1.
For instance, this connected DAG is not a directed tree: ({a, b, c}, {(a, b), (b, c), (a, c)}), since even if it is connected (more precisely weakly connected) it has semicycles, for instance (a, (a, b), b, (b, c), c, (a, c), a).
Likewise, for directed graphs:
- a directed forest is a directed graph without cycles (not to be confused with an acyclic directed graph, i.e. a DAG). In other words, it is a directed graph whose underlying graph is a forest.
- a branching (or out-forest) is a directed forest whose vertices have a maximum in-degree of 1;
- an anti-branching (or in-forest) is a directed forest whose vertices have a maximum out-degree of 1.
Another convention calls a directed tree a polytree, an arborescence a directed tree, a directed forest a polyforest and a branching a directed forest.
Cf. the documentation of NetworkX, a Python library.
Such a set $S$ is called a feedback vertex set, and the Wikipedia article mentions that it remains NP-hard even for very sparse directed graphs: even when each vertex has at most two edges going in, and at most two edges going out.
This makes it unlikely that there are nontrivial special cases that are easy. But it's known (Chen, Liu, Lu 2007) that the problem for all directed graphs is fixed-parameter tractable in the following sense: if you are given a fixed value $k$ and want to know if there's a feedback vertex set of size $\le k$, then there's an algorithm that's polynomial in $n$, the number of vertices in the graph. (But with a horrible dependency on $k$.)
Best Answer
No, this is not a structured graph. Any undirected graph can be represented by some starting DAG and making all edges undirected.
Any undirected graph G can be transformed into a DAG (and therefore back again by making the edges undirected) by choosing a total order for its vertices and directing every edge from the earlier endpoint in the order to the later endpoint. A total order can be obtained by assigning to each newly visited vertex along a DFS of G the value of an incrementing counter.
Making all edges undirected basically removes the only two properties (directed and acyclic) separating a DAG from an arbitrary undirected graph.