We develop a structural approach to simultaneous embeddability in temporal sequences of graphs, inspired by graph minor theory. Our main result is a classification theorem for 2-connected temporal sequences: we identify five obstruction classes and show that every 2-connected temporal sequence is either simultaneously embeddable or admits a sequence of improvements leading to an obstruction. This structural insight leads to a polynomial-time algorithm for deciding the simultaneous embeddability of 2-connected temporal sequences.

A weak deletion sequence is a sequence ( G 1 , … , G n ) of graphs so that for each i ∈ [ n − 1 ] either G i is isomorphic to a subgraph of G i + 1 , or vice versa: G i + 1 is isomorphic to a subgraph of G i . We prove that determining the simultaneous planar embeddability of weak deletion sequences of 2-connected graphs is NP-hard.