A Graph Minors Approach to Temporal Sequences

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.