  We study the computational complexity of determining structural properties of
edge periodic temporal graphs (EPGs). EPGs are time-varying graphs that
compactly represent periodic behavior of components of a dynamic network, for
example, train schedules on a rail network. In EPGs, for each edge $e$ of the
graph, a binary string $s_e$ determines in which time steps the edge is
present, namely $e$ is present in time step $t$ if and only if $s_e$ contains a
$1$ at position $t \mod |s_e|$. Due to this periodicity, EPGs serve as very
compact representations of complex periodic systems and can even be
exponentially smaller than classic temporal graphs representing one period of
the same system, as the latter contain the whole sequence of graphs explicitly.
In this paper, we study the computational complexity of fundamental questions
of the new concept of EPGs such as what is the shortest traversal time between
two vertices; is there a time step in which the graph (1) is minor-free; (2)
contains a minor; (3) is subgraph-free; (4) contains a subgraph; with respect
to a given minor or subgraph. We give a detailed parameterized analysis for
multiple combinations of parameters for the problems stated above including
several parameterized algorithms.
