Hardness of Planarity for Weak Temporal Sequences of 2-Connected Graphs

Abstract

A weak deletion sequence is a sequence $(G_1,\dots ,G_n)$ of graphs so that for each $i\in [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.

21 pages, 9 figures