Enumerate all paths in a given series-parallel graph
Treat SPG as DAG
We can see easily that every path from the source to the sink in a series-parallel graph (SPG) always goes nearer and nearer to the sink. It can never go backwards. There is no sideways. For the example in the illustration provided in the question, it can never move &quot;up&quot;. This phenomenon can be proved easily by structural induction.
So we can view a SPG as a directed acyclic graph (DAG) naturally, where every edge is assigned the direction such that its head is nearer to the sink than its tail. For the SPGs in the illustration of the question, the head of an edge is lower than its tail.
Many Algorithms for DAG
There have been many algorithms that lists all paths from a source node to a destination node in a DAG such as this one and this one.
Time-complexity and space-complexity
For simplicity, assume the given SPG is a simple graph. (The case of multi-graph is not much different.) We have $|E|\le2|V|-3$. This inequality will not be used here; it is shown just to illustrate an SPG is a relatively simpler graph.
What is the maximum number of paths from source to sink in an SPG of $n$ vertices?
A rough estimate is $2^{\Omega(n)}$. In fact, we can show that the maximum number of paths from source to sink in an SPG of $n$ vertices is $3^{4 - (n-2)\%5}4^{\lfloor(n-17)/5\rfloor +(n+3)\%5}$ for all $n\ge13$, which is $\Theta(4^{n/5})$. So the worst time-complexity for all algorithms is about $\Omega(n4^{n/5})$.
If the algorithm stores that all paths in full detail before outputting anything or if the space used by output is counted towards usages, then the space-complexity is $O(n4^{n/5}$). However, if the space used by output is not counted towards space-complexity, the space-complexity can be reduced to $O(n)$ if we use a depth-first search such as the following code in Python, assuming the adjacency list of the SPG is given in the input.
def list_paths(g, path):
    children = g[path[-1]]
    if len(children) == 0:
        print(path)
    else:
        for node in children:
            path.append(node)
            list_paths(g, path)
            path.pop()


&quot;&quot;&quot; 
Output all maximal paths from source in O(n)-working-space-complexity.
The parameter g is assumed to be an adjacency list that represents a valid DAG. 
&quot;&quot;&quot;

    
def list_all_paths(g, source):
    list_paths(g, [source])


g = {1: [2, 3],
     2: [4, 5, 6],
     4: [7],
     5: [7],
     6: [7],
     7: [8],
     3: [8],
     8: [9],
     9: [10, 11],
     10: [12],
     11: [13],
     12: [14],
     13: [14],
     14: [],
     }

list_all_paths(g, 1)

&quot;&quot;&quot; Expected Output
[1, 2, 4, 7, 8, 9, 10, 12, 14]
[1, 2, 4, 7, 8, 9, 11, 13, 14]
[1, 2, 5, 7, 8, 9, 10, 12, 14]
[1, 2, 5, 7, 8, 9, 11, 13, 14]
[1, 2, 6, 7, 8, 9, 10, 12, 14]
[1, 2, 6, 7, 8, 9, 11, 13, 14]
[1, 3, 8, 9, 10, 12, 14]
[1, 3, 8, 9, 11, 13, 14]
&quot;&quot;&quot;


By the way, the number of all paths can be computed directly in $O(n)$ time and $O(n)$ space by either recursive dynamic programming or iterative dynamic programming following a topological sort.

Exercise 1. Show the maximum number of paths from source to sink in an SPG of $n$ vertices is $3^{4 - (n-2)\%5}4^{\lfloor(n-17)/5\rfloor +(n+3)\%5}$ for all $n\ge13$, where $\%$ is the remainder operator. (For $n=12$, the maximum number is $4\times5=20$)


Exercise 2.  Verify the algorithm above in Python still works if the given DAG g is not a simple graph, i.e., that might be parallel edges. What is its time-complexity and working-space-complexity when $g$ is a SPG that is not necessarily a simple graph?