Space-Efficient Hierholzer

Eulerian cycles in O(m) time and O(n lg m) bits of working space — a step-by-step walkthrough.

Ziad Ismaili Alaoui, Detlef Plump, Sebastian Wild. SOSA 2026. paper · arXiv:2508.05251

step 0 / 0
Speed
Start
Pick a graph below, or step through the example from the paper.

Graph — conceptual edge colouring; the current vertex has a double border

Eulerian cycle written so far — edges leave the algorithm in this order

Algorithm — Space-Efficient-Hierholzer

Working memory — four O(lg m)-bit words per vertex

Adjacency lists and their iterators — one cursor per vertex sweeps Γ− and then Γ+; next[u] is its position

Graph input & examples
Examples
Random

Paste a graph in the algs4 format produced by the graph editor — V and E, then one u v line per directed edge, optionally followed by V lines of x y coordinates. CS Academy <Graph nodes={…} edges={…} /> markup is accepted too. Vertices are 0-based on input; the graph must be Eulerian (strongly connected, and d+(v) = d−(v) everywhere).

Neighbour order
Self-tests

Checks the simulation against the worked example in the paper (Figure 3) and against the defining properties of an Eulerian cycle on randomly generated graphs.

Not run yet.