Where is it shown how to construct a decomposition tree for a series-parallel graph in linear time? 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?
 A: 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.
A: I think David Speyer's answer is already good enough, but I thought I'd add as a separate answer that I have an old paper with an alternative method of recognizing series parallel graphs and their decomposition trees: Parallel recognition of series parallel graphs, D. Eppstein, Information & Computation 98:41-55, 1992.
The basic idea is to decompose the 2-connected components of the graph into a cycle and a sequence of paths, where the endpoints of each path belong to earlier pieces of the decomposition — this is called an "ear decomposition", is easy to find in linear time, and dates back to Whitney 1932. It turns out that a graph is 2-connected if and only if (in all possible ear decompositions) the two endpoints of each path belong to a single previous component and the intervals in each component formed by pairs of endpoints of paths are nested. The nesting structure lets one reconstruct the decomposition tree.
The paper is primarily about a model of parallel computing that very few people care about any more but it also provides conventional linear time algorithms.
A: As you state, Valdes/Tarjan/Lawler is a recognition algorithm.
There has been a stream of work on actually finding modular decompositions.  The recent work of Fabien de Montgolfier (with collaborators) is pretty definitive; they have also produced a C implementation.  I did a Perl implementation of an older algorithm, and Nathann Cohen is currently working to incorporate de Montgolfier's code into the Sage framework (it looks like it should appear in version 4.5.2, due early August 2010).
A: The answer can be found in Bodlaender, Fluiter 1996 "Parallel algorithms for series parallel graphs". They construct an sp-tree from an input graph if it is series-parallel.
[I know the question is three years old, but if that answer had been posted on this page, this would have saved me a lot of work. That's why I found it reasonable to answer it here, even now.]
A: This answer might be slightly overkill (and possibly underkill), but here goes.  For any fixed constant $k$, there is a linear-time algorithm to recognize if a graph $G$ has tree-width at most $k$, and if so to construct a tree-decomposition of $G$ of width at most $k$.  This was proven by Bodlaender in this paper.  Note that series-parallel graphs have tree-width at most 2.  Therefore, using the above algorithm of Bodlaender, for any series-parallel graph $G$, we can compute a tree-decomposition of $G$ of width at most 2 in linear-time.  This tree-decomposition is not exactly what you are looking for (hence the underkill part of the answer), but I think that you may be able to recover your "decomposition tree" from it (although I haven't thought about this carefully).  
