![[Figure 1 in CCC] shows two possible temporal spanners (left and right) of a same graph $\mathcal{G}$ (middle).](attachment:beebbd8e-2c03-43e8-b803-37d032ac2193:image.png)
This area of research explores the temporal analogue of spanning trees—that is, minimal-size subgraphs such that each pair of vertices reaches one another. In undirected static graphs, such a subgraph is always a tree. In temporal graphs this is not the case and these subgraphs are therefore referred to more generally as temporal spanners.
<aside>
Definition. (temporal spanner) [from CCC25]
Let $\mathcal{G} = ((V, E), \lambda)$ be a temporal graph.
A temporal subgraph $\mathcal{G}'\subseteq \mathcal{G}$ is a temporal graph $\mathcal{G}' = ((V', E'), \lambda')$ such that $V'\subseteq V$, $E'\subseteq E\cap V' \times V'$, and $\lambda'$ is a subset of $\lambda$ restricted to $E'$. If $\mathcal{G}\in \mathsf{TC}$, $V'=V$, and $\mathcal{G}'\in\mathsf{TC}$, then $\mathcal{G}'$ is a temporal spanner of $\mathcal{G}$.
</aside>
[Figure 1 in CCC] shows two possible temporal spanners (left and right) of a same graph $\mathcal{G}$ (middle).
When studying temporal spanners, researchers typically focus on two main directions: the computational complexity of finding a minimum-size temporal spanner, and the structural properties or size bounds of such spanners—both in general temporal graphs and within restricted classes. At the moment the literature primarily concentrates on the latter, especially on identifying classes of temporal graphs that guarantee sparse spanners and characterizing the structural conditions under which linear or near-linear spanners can exist.
The following provides an overview of the papers that have been written in regards to temporal spanners:
A related but distinct line of research investigates temporal spanning trees, also called multicast trees. Even though not every temporal graph admits a tree as a temporal spanner, this strand focuses on finding spanning temporal subgraphs with trees as their footprint—typically rooted at a single source—under optimization criteria such as earliest arrival or minimum weight. More on that topic can be found here:
Minimum Temporal Spanning Trees (Multicast Trees)
This section provides a summary of the state of the art on the structure of temporal spanners.
<aside>
Conclusion:
In general temporal graphs, no sparse spanners can be guaranteed: some temporal graphs require all $\Theta(n^2)$ edges for connectivity. However, in structured cases, especially when the footprint is a complete graph, sparse or even linear-size spanners are possible.
(May 2025) To this day it remains open whether temporal cliques always admit a linear-sized spanner.
It has been shown that the following sub-classes of cliques do:
Based on the negative answer for general temporal graphs, it is natural to ask whether certain classes of temporal graphs always admit sparse spanners.
For temporal cliques—complete graphs with arbitrary labelings—Casteigts, Peters, and Schoeters showed that O(n log n)-sparse spanners always exist. The most constrained and challenging case is when the labeling is both simple and proper, as these restrictions minimize redundancy in temporal paths. This setting is the focus of much of the current work on temporal spanners.
<aside>
Definition. (temporal clique) A temporal graph $\mathcal{G}=(V,E,\lambda)$ is a temporal clique if its footprint is a complete graph and $\lambda$ is proper and simple.
</aside>
The O(n log n) result from CCC (2019) combines multiple techniques: