Series–parallel graph

The series composition Sc = Sc(X,Y) of two TTGs X and Y is a TTG created from the disjoint union of graphs X and Y by merging the sink of X with the source of Y.

Finally, a graph is called series–parallel (SP-graph), if it is a TTSPG when some two of its vertices are regarded as source and sink.

In a similar way one may define series–parallel digraphs, constructed from copies of single-arc graphs, with arcs directed from the source to the sink.

[3] Series parallel graphs may also be characterized by their ear decompositions.

Besides being a model of certain types of electric networks, these graphs are of interest in computational complexity theory, because a number of standard graph problems are solvable in linear time on SP-graphs,[7] including finding of the maximum matching, maximum independent set, minimum dominating set and Hamiltonian completion.

The generalized series–parallel graphs (GSP-graphs) are an extension of the SP-graphs[8] with the same algorithmic efficiency for the mentioned problems.