Hardness of planarity for weak temporal sequences of 2-connected graphs
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.
Authors
- Johannes Carmesin (ORCID: https://orcid.org/0000-0002-3026-6673)
- Will J. Turner
Institutions
- TU Bergakademie Freiberg (DE)
Publication Details
- Journal
- Theoretical Computer Science
- Published
- 2026-02-21
- DOI
- https://doi.org/10.1016/j.tcs.2026.115825
- Primary Topic
- Advanced Graph Theory Research
- Type
- article
- Field-Weighted Citation Impact
- 0.00