# Series-parallel duality and read-once functions

If you draw a series-parallel multigraph in the plane, with an extra edge (the dashed edge below) connecting its two terminals, then its planar dual is also a drawing of the same type, turned sideways. The terminals of the dual are the vertices linked by the dual of the dashed edge. Each series composition in the primal turns into a parallel composition in the dual, and vice versa. Often one talks only about series-parallel graphs, not multigraphs, but for this duality the "multi" part is not easily avoidable: the primal or dual (or both) will have multiple edges between the same two vertices.

The same duality relates terminal-to-terminal paths (or, if you prefer, cycles through the dashed edge) and cuts (minimal subsets of edges whose removal separates the two terminals: a path in one graph is a cut in the dual and vice versa. This works regardless of whether one views the graphs as directed or undirected (the simple paths and minimal cuts are the same). Each pair of a primal and dual path cross exactly once. This one-crossing property is true more generally for *st*-planar digraphs, but *st*-planar graphs don't have the path-cut duality: some of their cuts might not be dual paths (see e.g. the cut formed by the two light green edges below left). On the other hand the path-cut duality works for undirected planar graphs (with two specified terminals and the same extra dashed edge trick to get corresponding terminals in the dual) but they don't generally have the one-crossing property (below right).

Now suppose that some edges might be open (you can go along them as part of a path) and others are closed (blocked off). This gives rise to a Boolean function that takes the state of each edge as input (open = true, closed = false) and produces an output that describes whether there exists an open route from one terminal to the other. The function can be expressed as a Boolean formula in which a series composition becomes an and-operation, and a parallel composition becomes an or-operation. The same function for the dual graph is just the negation of the function for the original graph, and can be obtained by negating all the edge variables and swapping ands for ors. I think this duality of Boolean functions is important for CMOS design but I'm not familiar with the details.

The Boolean function that you get this way has a special property: it is read-once, meaning that it has an expression with ands and ors in which each variable appears once (the expression that you get from the graph decomposition). After possibly negating some variables, every read-once function comes from a series-parallel graph in this way, the graph obtained by replacing the ands of a read-once expression by series compositions and the ors of a read-once expression by parallel compositions. If, instead, you express the same function in disjunctive normal form you get one prime implicant (conjunction) for each terminal-to-terminal path in the graph. And if you express the same function in conjunctive normal form you get one clause (disjunction) for each terminal-to-terminal path in the dual.

So the fact that the primal and dual paths of a series-parallel graph have a single crossing expresses, in a graph-theoretic form, a characteristic property of read-once functions (proven in at least three papers, some using these ideas): that their DNF implicants and CNF clauses always intersect in exactly one variable.