__
TR08-110 | 19th November 2008 00:00
__

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

**Abstract:**
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 we can make n, m, the denser is the graph.

For a given n, m, we 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 we reprove the

same result but in greater detail and relate that notion of series-parallel

to other popular notions of series-parallel. In particular, we show that

that notion is more general than minimal series-parallel and two terminal

series-parallel.