<aside>

============== Under Construction ==============

</aside>

This page introduces the fundamental definitions and notation for temporal graphs and serves as a global reference for all other pages.

Pages with more details on the concepts (such as earliest-arrival paths, connected components, …) are referenced below.

A temporal graph / time-varying network / scheduled network / *…* is a graph that changes predictably over time. In contrast to the area of dynamic algorithms where the changes to the network are not known in advance, usually local, and often even adversarial, a temporal graph changes in a predetermined, scheduled fashion and often undergoes global/drastic changes. For more details on other names of temporal graphs and the research areas they originated in, see History and Names of “Temporal Graphs”.

0. Notation (Quick Reference)

Definition of Temporal Graphs

Based on their scheduled nature, temporal graphs are usually defined via time labels:

<aside> ⚠️

Definition. [labeled representation]

A temporal graph is a pair $\mathcal{G}=(\, G=(V,E),\, \lambda\,)$ where:

• $G = (V, E)$ is called the footprint (static underlying graph) - directed or undirected;
• $\lambda\colon E \rightarrow 2^\Lambda$ is a time labeling function which assigns to every static edge $e\in E$ a set of time labels $\lambda(e)$ (also called presence times).

The lifetime $\Lambda$ is the largest time label.

A temporal edge is a pair $(e,t)$ with $e\in E$ and $t\in \lambda(e)$. The set of all temporal edges is denoted by $\mathcal{E} := \{ (e,t) \mid e \in E,\; t \in \lambda(e) \}$.

This is the canonical definition used throughout the wiki.

</aside>

Equivalently, a temporal graph can be described as a sequence of static graphs:

<aside> 💡

Definition. [snapshot representation]

A temporal graph is a sequence $\mathcal{G} = \big( G_t = (V, E_t) \big)_{t \in \Lambda}$ of static snapshots $G_t$.

The two representations are equivalent via:

• $E_t := \{ e \in E : t \in \lambda(e) \}$,
• $\lambda(e) := \{ t \in \Lambda : e \in E_t \}$.

Temporal edges and lifetime are defined equivalently.

</aside>

Note that in theoretical analysis, both models are considered in parallel, in particular the notions of time labels and snapshots.

Temporal trips

A temporal path is a sequence of temporal edges: $\big( (e_1,t_1),\; (e_2,t_2),\; \dots,\; (e_k,t_k) \big)$ such that:

1. the static edges form a simple path in the footprint: $e_i = \{v_i, v_{i+1}\}$ or $e_i = (v_i, v_{i+1})$, and
2. the times are non-decreasing: $t_1 \le t_2 \le \dots \le t_k$.

If the times are strictly increasing: $t_1 < t_2 < \dots < t_k$, the path is called strict, otherwise it is called non-strict.

Detailed path algorithms (earliest-arrival, minimum-duration, strict vs non-strict reachability, BFS variants, etc.)

👉 See the page: Temporal Paths/Trips/Journeys

Temporal reachability

A vertex u reaches v if there exists a temporal path from u to v: $u \rightsquigarrow v$. Two vertices are compatible $u \equiv_R v \Leftrightarrow u \rightsquigarrow v \text{ and } u \rightsquigarrow v$$u \equiv v \Leftrightarrow u \rightsquigarrow v \text{ and } u \rightsquigarrow v$.

This captures a temporal analogue of strong connectivity of directed graphs.

The reachability graph $\mathcal{R}(\mathcal{G})$ is a static edge with vertices $V$ and an edge $(u\rightarrow v)$ iff there is a temporal path from $u$ to $v$. Note that the reachability graph under strict reachability can differ from the reachability graph under nonstrict reachability.