Temporal Intersection Graphs

Temporal graphs are a valuable formalism for modelling real-world networks that evolve over time, but even those computational problems that are efficiently solvable on static graphs often become intractable when a temporal dimension is added.

This project will investigate a relatively unexplored way of restricting the structure of temporal graphs in the hope of recovering tractability for some problems, looking at temporal intersection graphs in which the graph is generated by a collection of geometric objects that appear and disappear and/or move over time.

This will build on the substantial literature on the tractability of computational problems restricted to static graphs generated by the intersections of geometric objects.