Runtime of Tucker's algorithm for generating a Eulerian circuit What is the time complexity of Tucker's algorithm for generating a Eulerian circuit? 
The Tucker's algorithm takes as input a connected graph whose vertices are all of even degree, constructs an arbitrary 2-regular detachment of the graph and then generates a Eulerian circuit.

I couldn't find any reference that says, for example, how the algorithm constructs an arbitrary 2-regular detachment of the graph, what data structures it uses, what the time complexity is, and so on. Any ideas?
A version of Tucker's algorithm was used in B. Awerbuch, A. Israeli, and Y. Shiloach, Finding Euler Circuits in Logarithmic Parallel Time, STOC 1984, to find Euler tours efficiently in parallel, and similar ideas can be used to make the algorithm run sequentially in linear time.

Suppose you have a connected graph $G$ in which all vertices have even degree, and start by pairing off edges at each vertex. This forms a collection of cycles that together cover the graph, and Tucker's algorithm works by joining the cycles together one at a time.

To make this repeated joining process efficient, first run a connected components algorithm (e.g. DFS) to find which edges belong to which cycles. Make a bipartite multigraph $H$, where the vertices on one side of the bipartition correspond one-for-one with the vertices of $G$, the vertices on the other side of the bipartition correspond with the cycles you've constructed, and the edges of $H$ correspond to incidences between cycles and vertices in $G$. Construct a spanning tree $T$ of $H$ (e.g. DFS again), rooted at one of the cycle vertices.

Now, for each cycle $C$ that is not the root of $T$, join $C$ to its grandparent in $T$ (by swapping the edge pairing at the common vertex of the two cycles, represented by the parent of $C$), in constant time per join.

The same technique also works for directed graphs (and that's the version that Awerbuch et al use for their main presentation); in that case, the only difference is that you want equally many incoming and outgoing edges at each vertex, and the edge-pairing at each vertex must pair incoming edges with outgoing edges.