  We study the problem of finding an Euler tour in an undirected graph G in the
W-Streaming model with O(n polylog(n)) RAM, where n resp. m is the number of
nodes resp. edges of G. Our main result is the first one pass W-Streaming
algorithm computing an Euler tour of G in the form of an edge successor
function with only O(n log(n)) RAM which is optimal for this setting (e.g., Sun
and Woodruff (2015)). The previously best-known result in this model is
implicitly given by Demetrescu et al. (2010) with the parallel algorithm of
Atallah and Vishkin (1984) using O(m/n) passes under the same RAM limitation.
For graphs with \omega(n) edges this is non-constant. Our overall approach is
to partition the edges into edge-disjoint cycles and to merge the cycles until
a single Euler tour is achieved. Note that in the W-Streaming model such a
merging is far from being obvious as the limited RAM allows the processing of
only a constant number of cycles at once. This enforces us to merge cycles that
partially are no longer present in RAM. Furthermore, the successor of an edge
cannot be changed after the edge has left RAM. So, we steadily have to output
edges and their designated successors, not knowing the appearance of edges and
cycles yet to come. We solve this problem with a special edge swapping
technique, for which two certain edges per node are sufficient to merge tours
without having all of their edges in RAM. Mathematically, this is controlled by
structural results on the space of certain equivalence classes corresponding to
cycles and the characterization of associated successor functions. For example,
we give conditions under which the swapping of edge successors leads to a
merging of equivalence classes.
