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?

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?