2026-07-20T05:36:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24933 2026-02-09T08:02:16Z ddc:004 open_access

Structural Parameterizations of Simultaneous Planarity Depian, Thomas Fink, Simon D. Firbas, Alexander Ganian, Robert Pfretzschner, Matthias Rutter, Ignaz SEFE Simultaneous Planarity Fixed-Parameter Tractability NP-hardness Given a set of graphs on the same vertex set, the problem Simultaneous Embedding With Fixed Edges (SEFE) asks, whether there exist planar drawings of all input graphs, such that every pair of drawings coincides on their shared subgraph. It is known that SEFE is NP-complete [Elisabeth Gassner et al., 2006], even in the so-called sunflower case, where all pairs of input graphs have the same shared graph G_∩ [Marcus Schaefer, 2012]. Fink, Pfretzschner, and Rutter [Simon D. Fink et al., 2023] recently initiated the study of the parameterized complexity of SEFE in the sunflower case, mainly focusing on structural parameters of G_∩. In this work, we shift the focus towards parameters of the union graph G_∪ that contains the edges of all input graphs. On the positive side, we establish fixed-parameter tractability for the problem with respect to the feedback edge set number of G_∪. We complement this result by showing that it, surprisingly, remains NP-complete even if G_∪ has constant vertex cover number. These results settle two open questions posed by Fink et al. [Simon D. Fink et al., 2023]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Thomas Depian and Simon D. Fink and Alexander Firbas and Robert Ganian and Matthias Pfretzschner and Ignaz Rutter 2025 Is Part Of LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2025.25 urn:nbn:de:0030-drops-249332 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.25 eng https://creativecommons.org/licenses/by/4.0/legalcode