Notions of isomorphism and equivalence of temporal graphs serve as tools to compare individual temporal graphs as well as entire classes of temporal graphs.
In the static setting, graph isomorphism captures structural equivalence. In the temporal setting, defining "sameness" is more nuanced, since temporal graphs come with several definitional choices — directed vs. undirected, strict vs. non-strict, proper vs. arbitrary, and simple vs. multi-labeled (see Temporal Graph Settings) — each of which affects the structure that can be expressed.
One prominent application of temporal equivalence notions is comparing these temporal graph settings systematically:
When can every graph in one setting be transformed into an equivalent graph in another? The resulting quasi-ordering (hierarchies) have practical implications: positive algorithmic results in more expressive settings transfer to weaker settings, and hardness results in weaker settings propagate to stronger ones.
Every equivalence/isomorphism notion induces a quasi-ordering on the set of temporal graph settings.
<aside> 💡
Definition.
A quasi-ordering (or preorder) on a set $S$ is a binary relation $\leq$ that is reflexive ($a \leq a$) and transitive ($a \leq b$ and $b \leq c$ implies $a \leq c$). Unlike a partial order, it need not be antisymmetric: two distinct elements can satisfy $a \leq b$ and $a\geq b$ simultaneously (they are then called equivalent).
</aside>
Applied to temporal settings:
<aside> 💡
Definition.
We write $S \rightsquigarrow_X T$ if every graph in setting $S$ can be transformed into an $X$-equivalent graph in setting $T$ (where $X \in \{S, R, iR\}$ denotes support, reachability, or induced-reachability equivalence). This relation is reflexive and transitive, forming a quasi-order.
Settings $S$ and $T$ are equivalent under $X$ if $S \rightsquigarrow_X T$ and $T \rightsquigarrow_X S$; $T$ is strictly more expressive if $S \rightsquigarrow_X T$ but $T \not\rightsquigarrow_X S$; and they are incomparable if neither transformation exists.
</aside>
Bijective equivalence is not considered for the quasi-ordering, as it is too restrictive to yield interesting structure (essentially requiring isomorphic path sets).
Induced-reachability equivalence collapses the entire hierarchy: using the transformation: semaphore (composed with transformation: support-dilation), every temporal graph in any setting can be transformed into an induced-reachability-equivalent graph in the proper & simple setting. Since this setting is a subset of every other setting, all directed settings and all undirected settings are induced-reachability equivalent (CCS24, Theorem 6; Döring 2025, Section 4.3). Hence the interesting structure lies in the support and reachability quasi-orderings.