Finding Euler Tours in One Pass in the W-Streaming Model with $\mathcal{\O}(n\log n)$ Memory

We study the problem of finding an Euler tour in an undirected graph $G$ in the W-Streaming model with $\mathcal{O}(n\textnormal{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 $\mathcal 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 $\mathcal O(m/n)$ passes under the same RAM limitation.  For graphs with $\omega(n)$ edges this is non-constant. (The talk is based on joint work with Christian Glazik, Jan Schiemann.)