Two-Terminal Series–Parallel Graph¶
A source–sink edge network built recursively from single edges by terminal-preserving series and parallel joins.
Core Idea¶
A two-terminal series–parallel graph has designated source and sink vertices and can be built from a single edge by two terminal-preserving operations. A series join identifies one component's sink with the next component's source; a parallel join identifies both sources and both sinks. A complete recursive construction, not merely a reducible-looking subgraph, defines membership.[^ref-a65437af1675]
The qualifier matters. The broader, unrooted \(K_4\)-minor-free class should not be equated without conditions to a graph with specified terminals and a full series/parallel parse. A three-leaf star has no \(K_4\) minor but cannot be such a two-terminal network for any two chosen terminals because its third leaf edge lies on no source-to-sink path.[^ref-a65437af1675]
Scope of Application¶
In a reducible resistor network, each resistor is an edge and the two measurement nodes are terminals. MIT's worked four-resistor example reduces a series pair, then parallel branches, then an outer series connection. Its construction tree permits equivalent resistance to be evaluated bottom-up: resistances add in series and their reciprocals add in parallel.[^mit]
An edge-based directed activity network can instantiate the same graph structure. For a constructed example, let activity \(A\) of duration 2 precede a fork to independent activities \(B\) of duration 3 and \(C\) of duration 5, both ending at the same finish event. The parse is \(\operatorname{series}(A,\operatorname{parallel}(B,C))\); with enough resources to run \(B\) and \(C\) simultaneously, the critical-path duration is \(2+\max(3,5)=7\). Limited workers invalidate that makespan interpretation, not the graph construction. Original graph-algorithm work distinguishes edge-series-parallel multidigraphs from vertex-series-parallel digraphs; they are not entered as interchangeable aliases.[ref-64380ae55465][ref-a65437af1675]
Clarity¶
Naming the terminals and writing a full parse tree settle two ambiguities: whether all edges are generated by the allowed joins, and whether “series–parallel” means this rooted edge class or a broader minor-based/vertex-based convention. Low treewidth or the absence of a \(K_4\) minor alone does not supply a terminal-preserving construction for a specified pair.[ref-a65437af1675][ref-64380ae55465]
Manages Complexity¶
The parse replaces a many-edge graph with a tree of local operations. For a property with valid combining laws, each subnetwork can be summarized at its terminal interface: one equivalent resistance, or one longest-path duration in the directed activity case. The simplification is conditional; a decomposition does not magically provide a combining rule for every graph property or model resource contention across supposedly parallel tasks.[mit][ref-64380ae55465]
Abstract Reasoning¶
Given \(s,t\), seek a complete decomposition to terminal edges. A series split has an intermediate junction; a parallel split has components sharing both endpoints. If an edge dangles outside every \(s\)–\(t\) route, or a cross-link prevents completion, the proposed parse is not a TTSP witness. Once a parse is established, derive the appropriate application recurrence separately: series/parallel resistance uses sum/reciprocal sum, while directed critical-path length uses sum/maximum under independent parallel execution.[ref-a65437af1675][mit]
Knowledge Transfer¶
The graph constructors transfer literally between a physical resistor circuit and a directed activity-on-edge model, but the values and combining laws do not. A circuit's conductance law is not a scheduling rule, and a critical-path recurrence is not a circuit law. The graph identity remains domain-specific because edges, terminal gluing and a finite recursive parse are essential. A broader compose-and-evaluate skeleton is a future-prime question. No strict live DAG parent is proposed: Treewidth is an invariant, Directed Acyclic Graph excludes undirected circuit instances, and Electronic Circuit is an application rather than a graph-class genus.[ref-a65437af1675][ref-64380ae55465][^mit]
[^ref-a65437af1675]: Matthew Daniel Wales, Extremal Theory of Graph Minors and Related Topics, University of Cambridge PhD thesis (2022), Definition 6.12 and following qualified \(K_4\)-minor discussion, PDF pp.106–107. https://api.repository.cam.ac.uk/server/api/core/bitstreams/3d97d7ca-dda0-4aa2-9c39-714492351124/content . [^ref-64380ae55465]: Jacobo Valdes, Robert E. Tarjan and Eugene L. Lawler, “The Recognition of Series Parallel Digraphs,” SIAM Journal on Computing 11(2) (1982), original publisher abstract distinguishing vertex and edge series-parallel classes. https://epubs.siam.org/doi/10.1137/0211023 . [^mit]: MIT 6.061 Introduction to Electric Power Systems, instructor-authored Class Notes ch.1, eqs.(6)–(8) and Fig.11, pp.4–6. https://www.ocw.mit.edu/courses/6-061-introduction-to-electric-power-systems-spring-2011/d79822ef5fbdb21b1c44e1b3b8282453_MIT6_061S11_ch1.pdf .
Neighborhood in Abstraction Space¶
Two-Terminal Series–Parallel Graph sits in a moderately populated region (49th percentile for distinctiveness): it has near-neighbors but no dense thicket of look-alikes.
Family — Graph Structures & Combinatorial Objects (44 abstractions)
Nearest neighbors
- Hadwiger number — 0.88
- Biconnected Component — 0.87
- Graph Toughness — 0.87
- Tree (Graph Theory) — 0.86
- Comparability Graph — 0.86
Computed from structural-signature embeddings · 2026-10-08