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?

this, and you don't need to use caps (which are often interpreted as yelling). – Qiaochu Yuan Jul 22 '10 at 8:48