In graph theory, **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.

In this context, the term graph means multigraph.

There are several ways to define series-parallel graphs. The following definition basically follows the one used by David Eppstein.^{ [1] }

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 *X* and *Y* by merging 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 _{2}* with assigned terminals.

* Definition 1*. Finally, a graph is called

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.

The following definition specifies the same class of graphs.^{ [2] }

* Definition 2*. A graph is an SP-graph, if it may be turned into

- 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.

Every series-parallel graph has treewidth at most 2 and branchwidth at most 2.^{ [3] } 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 is a series-parallel graph.^{ [4] }^{ [5] } 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 to K_{4}.^{ [3] }

Series parallel graphs may also be characterized by their ear decompositions.^{ [1] }

SP-graphs may be recognized in linear time^{ [6] } 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,^{ [7] } 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.

The **generalized series-parallel graphs** (GSP-graphs) are an extension of the SP-graphs^{ [8] } 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.

In graph theory, a **planar graph** is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross each other. Such a drawing is called a **plane graph** or **planar embedding of the graph**. A plane graph can be defined as a planar graph with a mapping from every node to a point on a plane, and from every edge to a plane curve on that plane, such that the extreme points of each curve are the points mapped from its end nodes, and all curves are disjoint except on their extreme points.

In computer science and optimization theory, the **max-flow min-cut theorem** states that in a flow network, the maximum amount of flow passing from the *source* to the *sink* is equal to the total weight of the edges in the minimum cut, i.e. the smallest total weight of the edges which if removed would disconnect the source from the sink.

In graph theory, a **tree decomposition** is a mapping of a graph into a tree that can be used to define the treewidth of the graph and speed up solving certain computational problems on the graph.

This is a **glossary of graph theory terms**. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by edges.

In mathematics, and more specifically in graph theory, a **graph** is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called *vertices* and each of the related pairs of vertices is called an *edge*. Typically, a graph is depicted in diagrammatic form as a set of dots or circles for the vertices, joined by lines or curves for the edges. Graphs are one of the objects of study in discrete mathematics.

In graph theory, an undirected graph *H* is called a **minor** of the graph *G* if *H* can be formed from *G* by deleting edges and vertices and by contracting edges.

In optimization theory, **maximum flow problems** involve finding a feasible flow through a flow network that obtains the maximum possible flow rate.

In graph theory, a **cograph**, or **complement-reducible graph**, or ** P_{4}-free graph**, is a graph that can be generated from the single-vertex graph

In graph theory, the **treewidth** of an undirected graph is a number associated with the graph. Treewidth may be defined in several equivalent ways: the size of the largest vertex set in a tree decomposition of the graph, the size of the largest clique in a chordal completion of the graph, the maximum order of a haven describing a strategy for a pursuit-evasion game on the graph, or the maximum order of a bramble, a collection of connected subgraphs that all touch each other.

In graph theory, a **path decomposition** of a graph *G* is, informally, a representation of *G* as a "thickened" path graph, and the **pathwidth** of *G* is a number that measures how much the path was thickened to form *G*. More formally, a path-decomposition is a sequence of subsets of vertices of *G* such that the endpoints of each edge appear in one of the subsets and such that each vertex appears in a contiguous subsequence of the subsets, and the pathwidth is one less than the size of the largest set in such a decomposition. Pathwidth is also known as **interval thickness**, **vertex separation number**, or **node searching number**.

In graph theory, a **haven** is a certain type of function on sets of vertices in an undirected graph. If a haven exists, it can be used by an evader to win a pursuit-evasion game on the graph, by consulting the function at each step of the game to determine a safe set of vertices to move into. Havens were first introduced by Seymour & Thomas (1993) as a tool for characterizing the treewidth of graphs. Their other applications include proving the existence of small separators on minor-closed families of graphs, and characterizing the ends and clique minors of infinite graphs.

**Graph operations** produce new graphs from initial ones. They may be separated into the following major categories.

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 more specifically graph algorithms, to represent the triconnected components of a graph. The SPQR tree of a graph may be constructed in linear time and has several applications in dynamic graph algorithms and graph drawing.

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 the edges of *G* into two subgraphs, and the width of the decomposition is the maximum number of shared vertices of any pair of subgraphs formed in this way. The **branchwidth** of *G* is the minimum width of any branch-decomposition of *G*.

In graph theory, a branch of mathematics, a **clique-sum** is a way of combining two graphs by gluing them together at a clique, analogous to the connected sum operation in topology. If two graphs *G* and *H* each contain cliques of equal size, the clique-sum of *G* and *H* is formed from their disjoint union by identifying pairs of vertices in these two cliques to form a single shared clique, and then possibly deleting some of the clique edges. A *k*-clique-sum is a clique-sum in which both cliques have at most *k* vertices. One may also form clique-sums and *k*-clique-sums of more than two graphs, by repeated application of the two-graph clique-sum operation.

In graph theory, a **Halin graph** is a type of planar graph, constructed by connecting the leaves of a tree into a cycle. The tree must have at least four vertices, none of which has exactly two neighbors; it should be drawn in the plane so none of its edges cross, and the cycle connects the leaves in their clockwise ordering in this embedding. Thus, the cycle forms the outer face of the Halin graph, with the tree inside it.

In mathematics, and more specifically in graph theory, a **directed graph** is a graph that is made up of a set of vertices connected by edges, where the edges have a direction associated with them.

In graph theory, a branch of mathematics, an **apex graph** is a graph that can be made planar by the removal of a single vertex. The deleted vertex is called an apex of the graph. It is *an* apex, not *the* apex because an apex graph may have more than one apex; for example, in the minimal nonplanar graphs *K*_{5} or *K*_{3,3}, every vertex is an apex. The apex graphs include graphs that are themselves planar, in which case again every vertex is an apex. The null graph is also counted as an apex graph even though it has no vertex to remove.

In graph theory, the **modular decomposition** is a decomposition of a graph into subsets of vertices called **modules.** A module is a generalization of a connected component of a graph. Unlike connected components, however, one module can be a proper subset of another. Modules therefore lead to a recursive (hierarchical) decomposition of the graph, instead of just a partition.

In order-theoretic mathematics, a **series-parallel partial order** is a partially ordered set built up from smaller series-parallel partial orders by two simple composition operations.

- 1 2 Eppstein, David (1992). "Parallel recognition of series-parallel graphs" (PDF).
*Information and Computation*.**98**(1): 41–55. doi:10.1016/0890-5401(92)90041-D. - ↑ Duffin, R. J. (1965). "Topology of Series-Parallel Networks".
*Journal of Mathematical Analysis and Applications*.**10**(2): 303–313. doi:10.1016/0022-247X(65)90125-3. - 1 2 Brandstädt, Andreas; Le, Van Bang; Spinrad, Jeremy P. (1999).
*Graph classes: a survey*. SIAM Monographs on Discrete Mathematics. and Applications.**3**. Philadelphia, PA: Society for Industrial and Applied Mathematics. pp. 172–174. ISBN 978-0-898714-32-6. Zbl 0919.05001. - ↑ Bodlaender, H. (1998). "A partial
*k*-arboretum of graphs with bounded treewidth".*Theoretical Computer Science*.**209**(1–2): 1–45. doi:10.1016/S0304-3975(97)00228-4. hdl: 1874/18312 . - ↑ Hall, Rhiannon; Oxley, James; Semple, Charles; Whittle, Geoff (2002). "On matroids of branch-width three".
*Journal of Combinatorial Theory, Series B*.**86**(1): 148–171. doi:10.1006/jctb.2002.2120. - ↑ Valdes, Jacobo; Tarjan, Robert E.; Lawler, Eugene L. (1982). "The recognition of series parallel digraphs".
*SIAM Journal on Computing*.**11**(2): 289–313. doi:10.1137/0211023. - ↑ Takamizawa, K.; Nishizeki, T.; Saito, N. (1982). "Linear-time computability of combinatorial problems on series-parallel graphs".
*Journal of the ACM*.**29**(3): 623–641. doi:10.1145/322326.322328. S2CID 16082154. - ↑ Korneyenko, N. M. (1994). "Combinatorial algorithms on a class of graphs".
*Discrete Applied Mathematics*.**54**(2–3): 215–217. doi:10.1016/0166-218X(94)90022-1. Translated from*Notices of the BSSR Academy of Sciences, Ser. Phys.-Math. Sci.*, (1984) no. 3, pp. 109–111 (in Russian)

This page is based on this Wikipedia article

Text is available under the CC BY-SA 4.0 license; additional terms may apply.

Images, videos and audio are available under their respective licenses.

Text is available under the CC BY-SA 4.0 license; additional terms may apply.

Images, videos and audio are available under their respective licenses.