graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...

, series–parallel graphs are graphs with two distinguished vertices called ''terminals'', formed recursively by two simple composition operations. They can be used to model series and parallel electric circuits.

Definition and terminology

In this context, the term graph means

multigraph In mathematics, and more specifically in graph theory, a multigraph is a graph which is permitted to have multiple edges (also called ''parallel edges''), that is, edges that have the same end nodes. Thus two vertices may be connected by more ...

. There are several ways to define series–parallel graphs. The following definition basically follows the one used by

David Eppstein David Arthur Eppstein (born 1963) is an American computer scientist and mathematician. He is a Distinguished Professor of computer science at the University of California, Irvine. He is known for his work in computational geometry, graph algorit ...

. A two-terminal graph (TTG) is a graph with two distinguished vertices, ''s'' and ''t'' called ''source'' and ''sink'', respectively. The parallel composition ''Pc = Pc(X,Y)'' of two TTGs ''X'' and ''Y'' is a TTG created from the

disjoint union of graphs In graph theory, a branch of mathematics, the disjoint union of graphs is an operation that combines two or more graphs to form a larger graph. It is analogous to the disjoint union of sets, and is constructed by making the vertex set of the resu ...

''X'' and ''Y'' by

merging Merge, merging, or merger may refer to: Concepts * Merge (traffic), the reduction of the number of lanes on a road * Merge (linguistics), a basic syntactic operation in generative syntax in the Minimalist Program * Merger (politics), the comb ...

the sources of ''X'' and ''Y'' to create the source of ''Pc'' and merging the sinks of ''X'' and ''Y'' to create the sink of ''Pc''. 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''. The source of ''X'' becomes the source of ''Sc'' and the sink of ''Y'' becomes the sink of ''Sc''. A two-terminal series–parallel graph (TTSPG) is a graph that may be constructed by a sequence of series and parallel compositions starting from a set of copies of a single-edge graph '' K₂'' with assigned terminals. ''Definition 1''. 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.

Alternative definition

The following definition specifies the same class of graphs. ''Definition 2''. A graph is an SP-graph, if it may be turned into '' K₂'' by a sequence of the following operations: * Replacement of a pair of parallel edges with a single edge that connects their common endpoints * Replacement of a pair of edges incident to a vertex of degree 2 other than ''s'' or ''t'' with a single edge.

Properties

Every series–parallel graph has

treewidth In graph theory, the treewidth of an undirected graph is an integer number which specifies, informally, how far the graph is from being a tree. The smallest treewidth is 1; the graphs with treewidth 1 are exactly the trees and the forests. The gra ...

at most 2 and

branchwidth In graph theory, a branch-decomposition of an undirected graph ''G'' is a hierarchical clustering of the edges of ''G'', represented by an unrooted binary tree ''T'' with the edges of ''G'' as its leaves. Removing any edge from ''T'' partitions ...

at most 2. Indeed, a graph has treewidth at most 2 if and only if it has branchwidth at most 2, if and only if every

biconnected component In graph theory, a biconnected component (sometimes known as a 2-connected component) is a maximal biconnected subgraph. Any connected graph decomposes into a tree of biconnected components called the block-cut tree of the graph. The blocks a ...

is a series–parallel graph. The maximal series–parallel graphs, graphs to which no additional edges can be added without destroying their series–parallel structure, are exactly the 2-trees. 2-connected series–parallel graphs are characterised by having no subgraph

homeomorphic In the mathematical field of topology, a homeomorphism, topological isomorphism, or bicontinuous function is a bijective and continuous function between topological spaces that has a continuous inverse function. Homeomorphisms are the isomorphi ...

to K₄. Series parallel graphs may also be characterized by their

ear decomposition In graph theory, an ear of an undirected graph ''G'' is a path ''P'' where the two endpoints of the path may coincide, but where otherwise no repetition of edges or vertices is allowed, so every internal vertex of ''P'' has degree two in ''G''. An ...

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 In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by ...

, because a number of standard graph problems are solvable in linear time on SP-graphs, including finding of the

maximum matching Maximum cardinality matching is a fundamental problem in graph theory. We are given a graph , and the goal is to find a matching containing as many edges as possible; that is, a maximum cardinality subset of the edges such that each vertex is adj ...

maximum independent set In graph theory, an independent set, stable set, coclique or anticlique is a set of vertices in a graph, no two of which are adjacent. That is, it is a set S of vertices such that for every two vertices in S, there is no edge connecting the two ...

, minimum dominating set and

Hamiltonian completion The Hamiltonian completion problem is to find the minimal number of edges to add to a graph to make it Hamiltonian. The problem is clearly NP-hard in general case (since its solution gives an answer to the NP-complete problem of determining wheth ...

. Some of these problems are

NP-complete In computational complexity theory, a problem is NP-complete when: # it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryi ...

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 Translated from ''Notices of the BSSR Academy of Sciences, Ser. Phys.-Math. Sci.'', (1984) no. 3, pp. 109–111 with the same

algorithmic efficiency In computer science, algorithmic efficiency is a property of an algorithm which relates to the amount of computational resources used by the algorithm. An algorithm must be analyzed to determine its resource usage, and the efficiency of an algor ...

for the mentioned problems. The class of GSP-graphs include the classes of SP-graphs and

outerplanar graph In graph theory, an outerplanar graph is a graph that has a planar drawing for which all vertices belong to the outer face of the drawing. Outerplanar graphs may be characterized (analogously to Wagner's theorem for planar graphs) by the two fo ...

s. 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 In graph theory, a branch of mathematics, the triconnected components of a biconnected graph are a system of smaller graphs that describe all of the 2-vertex cuts in the graph. An SPQR tree is a tree data structure used in computer science, and ...

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.

References