their series–parallel structure, are exactly the 2-trees. 2-connected series–parallel graphs are characterised by having no subgraph homeomorphic to K4. Series parallel graphs may also be characterized by their ear decompositions. Computational complexity SP-graphs may be recognized in linear time and their series–parallel decomposition may be constructed in linear time as well. 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, including finding of the maximum matching, maximum independent set, minimum dominating set and Hamiltonian completion. Some of these problems are NP-complete for general graphs. The solution capitalizes on the fact that if the answers for one of these problems are known for two SP-graphs, then one can quickly find the answer for their series and parallel compositions. Generalization The generalized series–parallel graphs (GSP-graphs) are an extension of the SP-graphs with the same algorithmic efficiency for the mentioned problems. The class of GSP-graphs include the classes of SP-graphs and outerplanar graphs. GSP graphs may be specified by Definition 2 augmented with the third operation of deletion of a dangling vertex (vertex of degree 1). Alternatively, Definition 1 may be augmented with the following operation. The source merge S = M(X,Y) of two TTGs X and Y is a TTG created from the disjoint union of graphs X and Y by merging the source of X with the source of Y. The source and sink of X become the source and sink of P respectively. An SPQR tree is a tree structure that can be defined for an arbitrary 2-vertex-connected graph. It has S-nodes, which are analogous to the series composition operations in series–parallel graphs, P-nodes, which are analogous to the parallel composition operations in series–parallel graphs, and R-nodes, which do not correspond to series–parallel composition operations. A 2-connected graph is series–parallel if and only if there are no R-nodes in its SPQR tree. See also Threshold graph Cograph Hanner polytope Series-parallel partial order References Graph families Graph operations Planar graphs