Characterization for Series-Parallel Channel Graphs

A graph G is called an s-stage graph if the set of vertices can be partitioned into s disjoint subsets Vh · · · , Vs, and the set of edges partitioned into s -- 1 disjoint subsets E, · · ·, Es-i, such that edges in Ei connect vertices in V, to vertices in Vt+i. G is called an s-stage channel graph if each of V and Vs contain a single vertex, called the source and the sink, respectively, and if each vertex in V,, 1 i s, is incident to at least one edge each in Ei-1 and Ei. For convenience, we assume that vertices in the same subset form a column and the columns are ordered from left to right in the natural way. A channel graph is series-parallel (SP) if it can be obtained either by a series combination or a parallel combination of two smaller SP channel graphs, with the smallest such graph being an edge. A series combination of an s-stage channel graph G and a £-stage channel graph if is a horizontal union of G and H, with the last stage of G being identified with the first stage of H (thus, the new channel graph has s + t -- 1 stages). A parallel combination of two s-stage channel graphs G and H is a vertical union of G and H, with the first stage of G being identified with the first stage of H, and the last stage of G being identified with the last stage of H (the new channel graph remains sstage). 887