SeriesParallel

Series-parallel, in the context of graph theory and circuit analysis, refers to a class of graphs and networks built by recursively applying series and parallel composition to two-terminal graphs. A two-terminal graph starts with a single edge joining two distinguished vertices, called terminals s and t. In a series composition, two graphs are joined end-to-end by identifying the terminal of one with the starting terminal of the other, yielding a graph whose terminals are the outer s and t. In a parallel composition, two graphs are merged by identifying their respective terminals, so the two graphs share the same pair of terminals.

Two-terminal series-parallel graphs are exactly the graphs that can be formed by these operations starting from a single edge. Equivalently, they are graphs with no subgraph that is a subdivision of the complete graph K4. They have treewidth at most 2 and are planar, making them a well-behaved subclass of graphs for algorithmic purposes. The structure of a series-parallel graph can be represented by an SP-tree, which records the sequence of series and parallel operations used to construct the graph.

Recognition and construction of series-parallel graphs can be performed in linear time, enabling efficient algorithmic applications. In electrical engineering and network theory, the concept is used to model and simplify resistive networks: series and parallel reductions correspond to combining resistances in series and in parallel. In graph algorithms, many problems that are hard in general graphs become tractable on series-parallel graphs, including certain shortest-path, cut, and flow problems. The term is sometimes used interchangeably with two-terminal series-parallel networks, reflecting its origins inDuffin’s work on series-parallel networks from the 1960s.