A Lower Bound on the Size of Series-Parallel Graphs Dense in Long Paths

One way to quantify how dense a multidag is in long paths is to find the largest n,m such that whichever ¡Â n edges are removed, there is still a path from an original input to an original output with ¡Ã m edges - the larger the authors can make n,m, the denser is the graph. For a given n,m, they would like to lower bound the size such a graph, say in edges, at least when restricting to a particular class of graphs. A bound of §Ù(n lg m) was provided in [Val77] for one notion of series-parallel graphs. Here they reprove the same result but in greater detail and relate that notion of series-parallel to other popular notions of series-parallel.