I used [this generator algorithm][1] for DAGs (by Szabolcs):

    vertexCount = 5;
    edgeCount = 10;
    elems = RandomSample@PadRight[ConstantArray[1, edgeCount], vertexCount (vertexCount - 1)/2];
    adj = Take[FoldList[RotateLeft, elems, Range[0, vertexCount - 2]], All, 
               vertexCount]~LowerTriangularize~-1;
    g = AdjacencyGraph[adj, DirectedEdges -> True];
    
Removing redundant edges iteratively:

    new = Graph[Flatten[If[GraphDistance[EdgeDelete[g, #], First@#, 
                Last@#] < Infinity, {}, #] & /@ EdgeList@g], 
             VertexLabels -> "Name", ImagePadding -> 10];
    {HighlightGraph[g, new, VertexLabels -> "Name", ImagePadding -> 10], new}

![Mathematica graphics](https://i.sstatic.net/1ULXj.png)

For some graphs, the remaining graph is simply the path graph of the topologically sorted vertices:

![Mathematica graphics](https://i.sstatic.net/pnxZ3.png)


  [1]: http://mathematica.stackexchange.com/questions/608/how-to-generate-random-directed-acyclic-graphs