Temporal sequences are a minor-closed generalization of classical temporal graphs, introduced by Carmesin and Turner as a setting in which graph-minor methods can be applied to evolving graphs. Classically, a temporal graph is a sequence of static graphs on a fixed vertex set, where edges are added or deleted over time. Temporal sequences enlarge this model by allowing consecutive snapshots to be related by edge deletions and edge contractions. This page collects the core definition of temporal sequences, their relation to classical temporal graphs, and the main problems studied on them.
<aside> ❗
A temporal sequence is a sequence $(G_1, \dots, G_n)$ of static graphs such that for every $i \in [n-1]$, either $G_i \preceq G_{i+1}$ or $G_{i+1} \succeq G_i$, where $\preceq$ denotes the graph minor relation. Equivalently, each consecutive pair of snapshots is related by deleting edges, contracting edges, deleting isolated vertices, and relabelling vertices.
A temporal sequence may be denoted as $(G_1 \succeq G_2 \preceq G_3 \succeq \dots)$ to record the direction of each minor relation.
</aside>
Figure 1 in A Graph Minors Approach to Temporal Sequences showing a temporal sequence. $G_2$ is a minor of $G_1$ by deleting edge $7$ and contracting edge $4$.
Classical temporal graphs are recovered as the special case in which the minor relation between consecutive snapshots is restricted to edge deletions and their reverse operation, edge additions.
A subtle but important point in Carmesin–Turner's definition is that vertices may be relabelled under the minor relation, but edges may not. That is, snapshot edges keep their identity through the sequence. Relaxing this gives the weak minor relation, where edge relabelling is allowed. The resulting weak temporal sequences behave worse algorithmically; see Hardness of planarity for weak temporal sequences of 2-connected graphs. This contrast is part of the motivation for using the labelled-minor notion as the base of temporal sequences.
From any temporal sequence, one may recursively delete entries $G_i$ for which the minor relations point in the same direction on both sides, for example $G_{i-1} \preceq G_i \preceq G_{i+1}$ or $G_{i-1} \succeq G_i \succeq G_{i+1}$. The resulting sequence is said to be in standard form: it alternates direction, starts with $\succeq$, ends with $\preceq$, and has odd-indexed entries as the local maxima, or "big" graphs. Temporal triples are sequences of the form $(G_1 \succeq G_2 \preceq G_3)$.
Given temporal sequences $(G_1, \dots, G_n)$ and $(H_1, \dots, H_n)$ of the same length, the latter is a temporal minor of the former if $H_i \preceq G_i$ for every $i \in [n]$. More generally, $(H_1, \dots, H_n)$ is a temporal minor of $(G_1, \dots, G_m)$ if $m \geq n$ and there is a partition $1 = a_1 < a_2 < \dots < a_n < a_{n+1} = m+1$ such that $H_i \preceq G_j$ for all $j \in [a_i, a_{i+1}-1]$.
Open Question 1. Is there a polynomial-time algorithm to decide whether one temporal sequence is a temporal minor of another?
A temporal sequence is called $x$-connected if every snapshot is $x$-connected.
Temporal sequences are designed to lift graph-minor intuition to evolving graph-like structures. The first major test case is planarity.
Given a temporal sequence, the problem of Simultaneous Embeddability of Temporal Sequences is to decide whether a temporal sequence admits a planar embedding that is compatible with the minor relations between consecutive snapshots.
Known landscape:
It is an open question whether it can be decided in polynomial if a temporal sequence is a temporal minor of another.
Question 1. Is there a polynomial-time algorithm deciding whether one temporal sequence is a temporal minor of another?
Question 2. Is there a polynomial-time algorithm deciding whether a temporal sequence has simultaneous tree-width at most $w$?
More generally, the same question can be asked for any structural minor-closed property: bounded path-width, bounded adhesion, series-parallel structure, outerplanarity, apex structure, or membership in a fixed minor-closed class.
Question 3. Can the planarity result be extended to simultaneous embeddability on other surfaces, such as the torus?
Questions 8.5 and 8.6. What are the right temporal-sequence analogues of simultaneous graphicness and simultaneous $k$-representability for matroids?
An affirmative answer for 2-connected co-graphic matroids follows from the polynomial-time result for 2-connected simultaneous embeddability.