The problem of simultaneous embeddability is a generalization of the planarity problem to Temporal Sequences.

Simultaneous embeddability asks for a temporal sequence whether we can find a planar embedding for every snapshot such that consecutive embeddings are consistent with relation to the changes occuring from $G_i$ to $G_{i+1}$. It is the first generalization of planarity testing to temporal graphs; more precisely to their generalization temporal sequences.

History on temporal connected components

1. Problem definition

<aside> ❗

Given a temporal sequence $\mathcal{G} = (G_1, \dots, G_n)$, the Simultaneous Embeddability problem asks whether there exist plane embeddings $\iota_i$ of $G_i$, for all $i$, such that the embeddings are compatible with the minor relations between consecutive graphs. That is

• if $G_i \preceq G_{i+1}$, then $\iota_i$ is the embedding induced by $\iota_{i+1}$ under the corresponding deletions and contractions;
• if $G_i \succeq G_{i+1}$, then $\iota_{i+1}$ is the embedding induced by $\iota_i$.

A sequence $(\iota_1, \dots, \iota_n)$ satisfying these conditions is a simultaneous embedding of $\mathcal{G}$.

</aside>

The problem is the natural analogue of graph planarity for temporal sequences. It is motivated by three points: (i) classical graph minor theory begins with planarity, via Kuratowski-type obstruction theorems; (ii) planarity is a clean test case for the additional constraints created by temporal structure; (iii) the problem generalises SEFE-style questions, where several graphs must be embedded consistently on shared structure.

2. Complexity landscape

Recall that a $x$-connected temporal sequence is $\mathcal{G} = (G_1, \dots, G_n)$ such that each $G_i$ is $x$-connected.

The 3-connected case is straightforward because every 3-connected planar graph has a unique embedding up to reorientation, by Whitney's theorem.

The connected case follows from the hardness of the SEFE$(3,1)$ problem. TODO

The difficult and structurally meaningful case is therefore the 2-connected case.

4. Main result

<aside> ❗

Theorem. Every nonempty 2-connected temporal sequence with two lists is either obstructed or admits an improvement.

</aside>

Iterating this theorem yields:

Corollary. There is a polynomial-time algorithm deciding simultaneous embeddability of 2-connected temporal sequences.

The result is not phrased simply as "embeddable iff no obstruction appears". Instead, the algorithm repeatedly simplifies the sequence. If an obstruction is found, the answer is NO. If no obstruction is present, an improvement is produced: a smaller analogue preserving the yes/no answer. Iterating improvements eventually reaches either an obstruction or the empty sequence.

5. Core embedding concepts

Rotation systems and induced embeddings

A rotation system $\sigma$ on a graph $G$ assigns to each vertex $v$ a cyclic order $\sigma(v)$ of the edges incident with $v$. For planar graphs, rotation systems encode plane embeddings up to orientation-preserving homeomorphism.