  We introduce a natural temporal analogue of Eulerian circuits and prove that,
in contrast with the static case, it is NP-hard to determine whether a given
temporal graph is temporally Eulerian even if strong restrictions are placed on
the structure of the underlying graph and each edge is active at only three
times. However, we do obtain an FPT-algorithm with respect to a new parameter
called interval-membership-width which restricts the times assigned to
different edges; we believe that this parameter will be of independent interest
for other temporal graph problems. Our techniques also allow us to resolve two
open question of Akrida, Mertzios and Spirakis [CIAC 2019] concerning a related
problem of exploring temporal stars. Furthermore, we introduce a vertex-variant
of interval-membership-width (which can be arbitrarily larger than its
edge-counterpart) and use it to obtain an FPT-time algorithm for a natural
vertex-exploration problem that remains hard even when
interval-membership-width is bounded.
