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?