There are two common ways to define a series-parallel graph (or 2-terminal series-parallel graph).


Definition 1


* start with K\_2 marking both vertices as terminals
* repeatedly join two smaller 2-terminal s/p graphs either in series or in parallel


Definition 2


* start with K\_2
* repeatedly replace a single edge by two in series or two in parallel


A "decomposition tree" for an s/p graph shows how it is constructed according to Definition 1; each node of the tree is a s/p graph and the children of each node are the components from which that graph was built by series or parallel composition.


It is well known that a series-parallel graph can be recognized in linear time; the usual reference to this is Valdes, Tarjan and Lawler (Valdes, Jacobo; Tarjan, Robert E.; Lawler, Eugene L. The recognition of series parallel digraphs. SIAM J. Comput. 11 (1982), no. 2, 298--313.)


It is also frequently *stated* in the literature that the decomposition tree can be found in linear time, either just as an assertion or with a reference to the same Valdes/Tarjan/Lawler paper.


*However*, when you actually read Valdes, Tarjan and Lawler, they do *not* construct the decomposition tree in linear time, but rather they run "Definition 2" in reverse and work on *reducing* the graph to a single edge by series and parallel reductions. So they *recognize* that the graph is s/p but they do not actually give the decomposition tree. 


Does anyone know if there is an explicit reference in the literature to actually *constructing* the sp-tree for a series-parallel graph in linear time?



Where is it shown how to construct a decomposition tree for a series-parallel graph in linear time?
It is easy enough to build the tree from a definition 2 description. Here is a sketch:


Suppose that SP graph $G$ occurs from subdividing graph $G'$ at an edge $e$, either in series or in parallel. Recursively, let $T'$ be the tree for $G'$. Then $e$ is a leaf of $T'$. Add two children below that leaf. Mark the node $e$ as either series or parallel according to whether the subdivision of $e$ was series or parallel.


I don't know what the efficiency of this is; it probably depends on your precise implementation of trees. And I don't know any references in the literature.


