The following is work in progress. If you realize that a paper is missing, find a mistake, or would like to contribute something, feel free to reach out: [email protected]

History of Temporal Graphs

Networks that change over time have been studied by different disciplines with diverse motivations. The following is a list of early research that is related to the present-day concept of temporal graphs (not considering the flow over time discussed by Ford and Fulkerson in 1962):

• 1966 Cooke and Halsey analysed shortest temporal trips where the travel times on every edge change over (discrete) time steps, are directed and can be set to $\infty$ to signify that this edge is not present at a certain time step.
• 1972-1995 and after Baker and Shostak; Hajnal, Milner and Szemerédi; Bumby; Awerbuch and Even; Hedetniemi, Hedetniemi and Liestman; Göbel, Cerdeira and Veldman; … researched Gossip Theory and broadcasting
  • What is the number of edges needed to realize a temporally connected graph (every vertex can reach every other vertex)
  • flooding/exploring a graph with information via phone calls
• 1974 Halpern and Priess computed shortest paths with time constraints: directed, travel time, edges close, “parking” (waiting at a node) occupies station, trains can still travel through but not “park”
  • temporal dijkstra - @Michelle Döring check
  • time-expanded network — define static expansion
• 1990 Orda and Rom and 1991 studied networks with time-dependent edge-lengths and shortest / minimum-delay / minimum-weight path therein.
• 1996 Berman discussed flows and computing paths in (un)directed (non)strict edge-scheduled networks
• 1997 Haray and Gupta defined the graph models: node- and edge-dynamic graphs

A lot happened in 2002/2003:

• 2002 Kempe, Kleinberg and Kumar first used the name of temporal networks and are usually cited as the beginning of “temporal graph theory”
• 2002 Ferreira and Viennot wrote a short note on evolving graphs which they also called dynamic network
• 2002 Köhler, Langkau and Skutella defined the static expansion for flows over time a problem closely related to temporal graphs
• 2002/2003 Bhadra and Ferreira first studied a variant of temporal connected components
• 2003 Cheng, Grossman and Lipman study time-stamped graphs and the associated influence digraph (reachability graph). They ask what graphs allow for reachability graphs with a fixed number of vertices and edges, and about realizability of reachability graphs.
• 2003 Xuan, Ferreira, Jarry computed shortest, fastest, and foremost temporal paths in what they call a dynamic network.

2010-2014 the study of temporal graph slowly grew into for fundamental questions apart from computing shortest paths. Surveys emerged, usage in different fields not associated with temporal graphs (e.g. reconfigurable networks and the directed grid theorem)

2015-2020 defining temporal graph problems (~15 papers per year)

2021 is the first year with ~30 papers
2022: ~30
2023: >30
2024: >40
2025: ~50

<aside>

The following is a database on the different names of the concept of “temporal graphs”. It also contains the (to our knowledge) first usage or mentioning of that name. If you believe one of those Who’s or When’s to be incorrect, let us know via [email protected]

</aside>

Names for temporal graphs, sorted by year