Space-Efficient Hierholzer for Undirected Graphs

We give a linear-time algorithm for finding an Eulerian tour of an undirected multigraph that uses only $O(n)$ words of working memory, rather than the $O(m)$ space a direct implementations of Hierholzer’s algorithm keeps around for the partial tour or an edge-centric DFS stack.

As in our previous work on space-efficient Hierholzer for directed graphs, we assume that the input graph is given in a read-only adjacency-array representation; edges are stored in both endpoints’ adjacency lists. The tour is written to an append-only stream in order.

The construction first finds a small skeleton: a spanning circuit with at most $2n$ edges. It then walks along the skeleton step by step, peeling off and immediately emitting further circuits rooted at each vertex as it is reached.
Together, the two results give matching $O(n)$-word space bounds for Eulerian tours of both directed and undirected multigraphs.

Try it out!   (Interactive demo)