Structural Parameterizations of
Simultaneous Planarity

We expand our understanding of the complexity of S-SEFE by settling both open questions listed above. As our first result, we answer Question (A) in the negative and prove:

The reduction underlying the proof of Theorem 1 is non-trivial and apart from a careful construction, it also relies on Vizing’s Theorem [58] and the edge coloring machinery introduced by Misra and Gries [48]. For our second result, we turn towards Question (B) which we answer positively:

We note that here a linear kernel means that we provide a polynomial-time procedure that reduces an instance of S-SEFE to an equivalent one whose size is linear in the feedback edge number of the union graph $G_{\cup }$. The result strictly improves upon the previously established kernel of Fink, Pfretzschner and Rutter [26], whose size depended both on the feedback edge number and $k$.

In our concluding discussion, we also provide new insights into the complexity-theoretic behavior of S-SEFE (and also SEFE) under other graph parameters. Notably, we rule out parameterized algorithms w.r.t. the graph degeneracy of the union graph, and establish an equivalence between treewidth and clique-width in the sense that algorithms and lower bounds for the considered problems transfer between these two parameters.

We need to show that $G_{xy}\cap G_{z\alpha }=G_{\cap }^{\ast }$ for each $xy,z\alpha \in E(\overrightarrow{G})$, implying that $G_{\cap }$ is well-defined and equal to $G_{\cap }^{\ast }$. Suppose not.

By construction, as $G_{\cap }^{\ast }$ is a subgraph of $G_{xy}$ and $G_{z\alpha }$, and the codomain of $i(\cdot )$ consists of even integers, this means $x{c}_{i(xy)}=z{c}_{i(z\alpha )}$ or $y{c}_{i(xy)+1}=\alpha c_{i(z\alpha )+1}$.

First, consider the case where $xy,z\alpha$ form a 2-cycle. Then, we have $\alpha =x$, $z=y$ and $j≔i(xy)=i(z\alpha )$. In case we have $x{c}_{i(xy)}=z{c}_{i(z\alpha )}$, this means $x=y$, i.e., arc $xy$ is a self-loop. As $\overrightarrow{G}$ does not have self-loops, this is a contradiction. Alternatively, in case we have $y{c}_{i(xy)+1}=\alpha c_{i(z\alpha )+1}$, this means $\alpha =z$, which again means $\overrightarrow{G}$ has a self-loop, a contradiction.

Otherwise $xy,z\alpha$ do not form a 2-cycle. First, if $x{c}_{i(xy)}=z{c}_{i(z\alpha )}$, we have $x=z$ and $i(xy)=i(z\alpha )$. But then, both $y$ and $\alpha$ are neighbors of $x$ in $G$. Additionally, $y\ne \alpha$, since otherwise, the two arcs would form a 2-cycle. Thus the edge coloring assigns $xy$ and $za$ different colors, which contradicts $i(xy)=i(z\alpha )$. The other case, $y{c}_{i(xy)+1}=\alpha c_{i(z\alpha )+1}$, is symmetric. $◀$

To make the notion of how to “read off” a topological ordering of $c_1^{\prime }s$ neighbors in a simultaneous embedding precise, we define:

Next, we make an observation that will help us prove the correctness of our reduction. Essentially, we have that each possible embedding of $G_{ab}$ tells us into which set of the 2-partition to assign $a$ and $b$, and a guarantee that, if we assign them to the same set, the order in which we will “read off” their ordering will be consistent with there being an arc $ab$ in the given 2-Digraph Coloring instance.

Now, we can show:

$(\Rightarrow ):$ Let $L\dot{\cup }R$ be a partition of $V(\overrightarrow{G})$ such that $\overrightarrow{G}[L]$ as well as $\overrightarrow{G}[R]$ are acyclic, and let ${\mathrm{\ell }}_1\prec \mathrm{\cdots }\prec {\mathrm{\ell }}_{|L|}$ and $r_1\prec \mathrm{\cdots }\prec r_{|R|}$ be a topological ordering of $G[L]$ and $G[R]$, respectively, where we call the former the left order and the latter the right order.

Towards finding a simultaneous embedding of the S-SEFE instance, we first fix a planar embedding of $G_{\cap }$. As $G_{\cap }$ is connected, it suffices to specify a rotation system. Note that, as $G_{\cap }$ is just a cycle with pendant vertices attached to $c_1$, any rotation system for $G_{\cap }$ yields a planar embedding. For each $c_i$ where $i\ne 1$, $c_i$ has only two neighbors and hence, there is only one choice for $c_i$’s rotation. For $c_1$, we define the following clockwise cyclic order of $N_{G_{\cap }}(c_1)$:

In other words, in the $c_2$-oriented $c_{15}$-delimited split of the rotation around $c_1$, the left-face order equals ${\mathrm{\ell }}_1\prec \mathrm{\cdots }\prec {\mathrm{\ell }}_{|L|}$, and the right-face order equals $r_1\prec \mathrm{\cdots }\prec r_{|R|}$.

It remains to find a planar embedding for each input graph $G_{ab}$, such that each embedding induces the same embedding on $G_{\cap }$. Consider $G_{ab}$ for $ab\in E(\overrightarrow{G})$. We select a suitable embedding of $G_{ab}$’s four embeddings listed in Figure 4 as follows: If $a,b\in L$ and we have $a\prec b$, we use embedding 1. ($b\prec a$ is impossible since ${\mathrm{\ell }}_1,\mathrm{\dots },{\mathrm{\ell }}_{|L|}$ is a topological ordering of $\overrightarrow{G}[L]$ and $ab\in E(\overrightarrow{G}[L])$). If $a,b\in R$ and we have $a\prec b$, we use embedding 2. ($b\prec a$ is impossible since $r_1,\mathrm{\dots },r_{|R|}$ is a topological ordering of $\overrightarrow{G}[R]$ and $ab\in E(\overrightarrow{G}[R])$). If $a\in L$ and $b\in R$, we use embedding 3. Finally, if $b\in L$ and $a\in R$, we use embedding 4.

In each case, it is easy to verify that the clockwise cyclic order of $c_1$ in $G_{ab}$ is a sub-order of the clockwise cyclic order of $c_1$ in $G_{\cap }$, the same holds for $c_{i(ab)}$ and $c_{i(ab)+1}$, and that the rotations for the remaining vertices coincide in the embedding of $G_{ab}$ and the embedding of $G_{\cap }$. Thus, as required, we have constructed a simultaneous embedding of the S-SEFE instance.

$(\Leftarrow ):$ Let a simultaneous embedding of the S-SEFE instance be given. Consider the $c_2$-oriented $c_{15}$-delimitted split of the clockwise order around $c_1$ in the planar embedding induced on $G_{\cap }$ by the simultaneous embedding. We denote the left-face order by ${\mathrm{\ell }}_1,\mathrm{\dots },{\mathrm{\ell }}_{|L|}$ (with vertex set $L$), and denote the right-face order by $r_1,\mathrm{\dots },r_{|R|}$ (with vertex set $R$). Observe that $L$ and $R$ form a partition of $V(\overrightarrow{G})$.

We claim that ${\mathrm{\ell }}_1\prec \mathrm{\cdots }\prec {\mathrm{\ell }}_{|L|}$ is a topological ordering of $\overrightarrow{G}[L]$ and that $r_1\prec \mathrm{\cdots }\prec r_{|R|}$ is a topological ordering of $\overrightarrow{G}[R]$, that is, $\overrightarrow{G}$ is a positive instance of 2-Digraph Coloring. For this to be the case, whenever $ab\in E(\overrightarrow{G})$ and $a,b\in L$ (resp. $a,b\in R$), we need $a\prec b$ in ${\mathrm{\ell }}_1\prec \mathrm{\cdots }\prec {\mathrm{\ell }}_{|L|}$ (resp. $r_1\prec \mathrm{\cdots }\prec r_{|R|}$). Let $ab\in E(\overrightarrow{G})$ and $a,b\in L$. Consider the planar embedding of $G_{ab}$ given by the simultaneous embedding of the S-SEFE instance. By Observation 5, we have $a\prec b$. The argument for the other order is symmetric. Hence, the proof is complete. $◀$

Finally, to obtain Theorem 1, we observe that the reduction can be performed in polynomial time, as the Misra–Gries edge-coloring algorithm is polynomial-time computable. Furthermore, by Lemma 3, the construction yields an S-SEFE instance satisfying the sunflower property. Moreover, the set $\{c_1,\mathrm{\dots },c_{15}\}$ forms a vertex cover of $G_{\cup }$, so $\mathrm{vc}(G_{\cup })\le 15$. Finally, S-SEFE is known to be in $\mathrm{𝖭𝖯}$ [32]. Thus, as our reduction is correct (Lemma 6), we obtain:

Let $ℐ$ be an instance of S-SEFE and ${ℐ}^{\prime }$ the instance that we obtain after applying Rule I. Furthermore, let $P$ be the ID2-path identified when applying the rule. We now show that $ℐ$ has a simultaneous embedding if and only if ${ℐ}^{\prime }$ does.

$(\Rightarrow ):$ Let $({ℰ}_1,\mathrm{\dots },{ℰ}_k)$ be a simultaneous embedding of $ℐ$. As $P$ consists solely of edges from $G_{\cap }$, it exists in every embedding ${ℰ}_i$, $i\in [k]$. We construct a simultaneous embedding of ${ℐ}^{\prime }$ by contracting $P$ into a single edge $uv$ in each embedding ${ℰ}_i$, $i\in [k]$. This way, we ensure that all the resulting embeddings agree on $G_{\cap }^{\prime }$. Finally, since planarity is preserved under edge contraction, we conclude that $({ℰ}_1^{\prime },\mathrm{\dots },{ℰ}_k^{\prime })$ is a simultaneous embedding of ${ℐ}^{\prime }$.

$(\Leftarrow ):$ Let $({ℰ}_1^{\prime },\mathrm{\dots },{ℰ}_k^{\prime })$ be a simultaneous embedding of ${ℐ}^{\prime }$. Recall that we introduced the edge $uv\in E(G_{\cap }^{\prime })$ in ${ℐ}^{\prime }$ that connects the two endpoints of $P$. Since $uv\in E(G_{\cap }^{\prime })$, the edge exists in every embedding ${ℰ}_i^{\prime }$, $i\in [k]$. We now reintroduce $P$ in each ${ℰ}_i^{\prime }$ by subdividing the edge $uv$ sufficiently many times and updating the embeddings accordingly, i.e., to reflect the subdivision process. Since the ${ℰ}_i^{\prime }$ induce the same embedding on $G_{\cap }^{\prime }$ before this operation, the obtained embeddings ${ℰ}_i$ do so on $G_{\cap }$ afterwards. Furthermore, subdividing an edge cannot destroy planarity, i.e., each ${ℰ}_i$ is a planar embedding and together they yield a simultaneous embedding of $ℐ$. $◀$

Let $ℐ$ be an instance of S-SEFE and ${ℐ}^{\prime }$ the instance that we obtain after applying Rule II. Furthermore, let $P$ denote the ID2-path and let $G_{i^{\ast }}$ be the graph identified when applying the rule. We now show that $ℐ$ has a simultaneous embedding if and only if ${ℐ}^{\prime }$ does.

$(\Rightarrow ):$ Let $({ℰ}_1,\mathrm{\dots },{ℰ}_k)$ be a simultaneous embedding of $ℐ$. We now modify each embedding ${ℰ}_i$, $i\in [k]$ and ensure that they yield the same embedding when restricted to $G_{\cap }^{\prime }$. For the embedding ${ℰ}_{i^{\ast }}$, since $E(P)\subseteq E(G_{i^{\ast }})$, we can again contract the path $P$ into the edge $uv$ to obtain an embedding ${ℰ}_{i^{\ast }}^{\prime }$ of $G_{i^{\ast }}^{\prime }$. For all other embeddings ${ℰ}_j$, $j\in [k]\setminus i^{\ast }$, we obtain an embedding ${ℰ}_j^{\prime }$ of $G_j^{\prime }$ by removing the internal vertices of $P$. Since planarity is preserved under edge contraction and vertex deletion, each ${ℰ}_i^{\prime }$ is a planar embedding of $G_i^{\prime }$, $i\in [k]$. Furthermore, as we remove the same edges from $G_{\cap }$ from each embedding ${ℰ}_i$, all ${ℰ}_i^{\prime }$, $i\in [k]$, agree on $G_{\cap }^{\prime }$ and witness the existence of a simultaneous embedding of ${ℐ}^{\prime }$.

$(\Leftarrow ):$ Let $({ℰ}_1^{\prime },\mathrm{\dots },{ℰ}_k^{\prime })$ be a simultaneous embedding of ${ℐ}^{\prime }$. We now re-insert the ID2-path $P$ into each embedding ${ℰ}_i^{\prime }$, $i\in [k]$. For ${ℰ}_{i^{\ast }}^{\prime }$, we can re-insert $P$ by subdividing the edge $uv$ sufficiently many times and updating the embedding to reflect the subdivision. This yields a planar embedding ${ℰ}_{i^{\ast }}$ of $G_{i^{\ast }}$, which induces a (new) embedding ${ℰ}_{\cap }$ on $G_{\cap }$. For all other embeddings ${ℰ}_j^{\prime }$, $j\in [k]\setminus i^{\ast }$, the fact that we could not apply Rule I tells us that there is at least one edge $e\in E(P)\setminus E(G_j)$. Hence, $P$ is not a single path in $G_j$ but a collection of paths and/or isolated vertices. Together with the fact that $P$ is an ID2-path in $G_{\cup }$, this allows us to freely choose the embedding of the internal vertices of $P$ and edges of $E(P)\cap E(G_{\cap })$ when we insert them into ${ℰ}_j^{\prime }$. In particular, we can choose the resulting embedding ${ℰ}_j$ such that its restriction to $G_{\cap }$ coincides with ${ℰ}_{\cap }$. Moreover, to see that ${ℰ}_j$ is a planar embedding, it suffices to observe that we can draw the internal vertices of $P$ and edges of $E(G_{\cap })$ arbitrarily close to $u$ or $v$, respectively. We conclude that the obtained embeddings ${ℰ}_i$, $i\in [k]$, form a simultaneous embedding of $ℐ$. $◀$

Let $ℐ$ be an instance of S-SEFE and ${ℐ}^{\prime }$ the instance that we obtain after applying Rule III. Furthermore, let $P$ be the ID2-path identified when applying the rule. We now show that $ℐ$ has a simultaneous embedding if and only if ${ℐ}^{\prime }$ does.

$(\Rightarrow ):$ Let $({ℰ}_1,\mathrm{\dots },{ℰ}_k)$ be a simultaneous embedding of $ℐ$. We now modify each ${ℰ}_i$, $i\in [k]$, to obtain a simultaneous embedding of ${ℐ}^{\prime }$. First, we remove the internal vertices of $P$ from each ${ℰ}_i$. If $E(G_i)\subseteq E(G_{\cap })\cup E(P)$, i.e., if every edge of $G_i$ belongs to $G_{\cap }$ or $P$, we can delete the entire embedding ${ℰ}_i$. Since we only deleted vertices (and their incident edges), the remaining embeddings ${ℰ}_i^{\prime }$ yield a simultaneous embedding of the corresponding sub-instance of $ℐ$. Let ${ℰ}_{\cap }^{\prime }$ be the resulting embedding of $G_{\cap }^{\prime }$. What is missing from a simultaneous embedding of ${ℐ}^{\prime }$ is the embedding ${ℰ}_P^{\prime }$ of the graph $G_P$. Recall that $E(G_P)=E(G_{\cap }^{\prime })\cup \{uv\}$, where $u$ and $v$ are the end vertices of $P$. We initialize ${ℰ}_P^{\prime }={ℰ}_{\cap }^{\prime }$. This ensures that all embeddings induce the same embedding when restricted to $G_{\cap }^{\prime }$. What is missing from an embedding of $G_P$ is the edge $uv$. We now show that vertices $u$ and $v$ must share a face in ${ℰ}_P^{\prime }={ℰ}_{\cap }^{\prime }$, which allows us to insert the edge $uv$. Towards a contradiction, assume that this would not be the case. We recall that ${ℰ}_{\cap }^{\prime }$ was obtained from ${ℰ}_{\cap }$ by vertex deletion. Hence, $u$ and $v$ do not share a face in ${ℰ}_{\cap }$ either. However, since $({ℰ}_1,\mathrm{\dots },{ℰ}_k)$ is a simultaneous embedding of $ℐ$, and $u$ and $v$ are connected by the ID2-path $P$ in $G_{\cup }$, there exists an edge $ab\in E(P)\cap E(G_i)$ for some $i\in [k]$ such that $a$ and $b$ do not share a face in ${ℰ}_{\cap }$. Since ${ℰ}_i$ is part of a simultaneous embedding of $ℐ$, this edge $ab$ crosses another edge in any drawing ${\mathrm{\Gamma }}_i$ represented by ${ℰ}_i$, a contradiction to the assumption that $({ℰ}_1,\mathrm{\dots },{ℰ}_k)$ is a simultaneous embedding. Therefore, $u$ and $v$ share a face in ${ℰ}_P^{\prime }$, i.e., we can insert the edge $uv$ in ${ℰ}_P^{\prime }$. This completes the construction of the simultaneous embedding of ${ℐ}^{\prime }$.

$(\Leftarrow ):$ Let $({ℰ}_1^{\prime },\mathrm{\dots },{ℰ}_{k^{\prime }}^{\prime })$ be a simultaneous embedding of ${ℐ}^{\prime }$ and consider ${ℰ}_P^{\prime }$. As $E(G_P)=E(G_{\cap }^{\prime })\cup \{uv\}$, the vertices $u$ and $v$ share a face in ${ℰ}_P^{\prime }$. Moreover, we can identify a face $f^{\ast }$ in ${ℰ}_{\cap }^{\prime }$ which is shared by $u$ and $v$ and contains the edge $uv$ (in ${ℰ}_P^{\prime }$).

We now construct a simultaneous embedding $({ℰ}_1,\mathrm{\dots },{ℰ}_k)$ of $ℐ$ as follows. Consider an input graph $G_i$, $i\in [k]$, and the embedding ${ℰ}_i^{\prime }$. For now, we assume that this embedding exists but note that our reduction rule could have removed $G_i$ entirely from $ℐ$. This case is handled at the end. Consider the face $f^{\ast }$ in the embedding ${ℰ}_i^{\prime }$ when restricted to $G_{\cap }^{\prime }$. Observe that by above arguments, the face $f^{\ast }$ contains both $u$ and $v$. Recall that we apply Rule III only if Rules I and II are not applicable. Hence, similar to the proof of Lemma 8, we observe that when induced on $G_i$, the ID2-path $P$ is not a single path between $u$ and $v$ but a collection of paths and/or isolated vertices. Hence, we can freely choose the embedding of the respective vertices and edges when extending ${ℰ}_i^{\prime }$ into an embedding ${ℰ}_i$ of $G_i$. In particular, we can ensure that all internal vertices of $P$ are inside the face $f^{\ast }$ (when ${ℰ}_i$ is restricted to $G_{\cap }$). Moreover, we can include the edges $ux,vy\in E(P)$ in the rotation around $u$ and $v$, respectively, such that they lie between the same shared edges as the edge $uv$ in ${ℰ}_P^{\prime }$; see Figure 6. This way we ensure that the constructed embeddings will agree on $G_{\cap }$. Furthermore, we can draw the internal vertices of $P$ and edges of $E(G_{\cap })$ arbitrarily close to $u$ or $v$, i.e., ${ℰ}_i$ is a planar embedding of $G_i$.

Finally, recall that our reduction rule can remove a $G_i$ from $ℐ$. However, since this only happens if $E(G_i)\setminus E(G_{\cap })\subseteq E(P)$, we can initialize ${ℰ}_i^{\prime }={ℰ}_{\cap }^{\prime }$ and proceed as above. Hence, we conclude that the constructed embeddings form a simultaneous embedding of $ℐ$. $◀$

With Lemmas 7, 8, and 9, we have all ingredients at hand to establish fixed parameter tractability of S-SEFE when parameterized by the feedback edge number of $G_{\cup }$. See 2

Let $ℐ=(G_1,G_2,\mathrm{\dots },G_k)$ be an instance of S-SEFE. Recall that we can assume $G_{\cup }$ to be biconnected thanks to known steps that simplify instances of S-SEFE [11]. Let us exhaustively apply Reduction Rules I–III of Kernel 1 to $ℐ$ to obtain ${ℐ}^{\prime }=(G_1^{\prime },G_2^{\prime },\mathrm{\dots },G_{k^{\prime }}^{\prime })$, $k^{\prime }\ge 1$, with union graph $G_{\cup }^{\prime }$. Note that the reduction rules maintain biconnectivity and the size of our parameter, i.e., the feedback edge number of $G_{\cup }$– we only replace paths where every internal vertex is of degree 2 in $G_{\cup }$ by a single edge.

Let $F\subseteq E(G_{\cup })$ be a minimum feedback edge set of $G_{\cup }^{\prime }$ of size $\mathrm{fen}(G_{\cup }^{\prime })=\mathrm{fen}(G_{\cup })$. We can compute $F$ in polynomial time by, for example, computing a spanning tree $T$ of $G_{\cup }^{\prime }$ and setting $F≔E(G_{\cup }^{\prime })\setminus E(T)$. As $G_{\cup }^{\prime }$ is biconnected, the graph $T≔G_{\cup }^{\prime }-F$ is a tree. To ease argumentation, we assume $T$ to be rooted at an arbitrary leaf. Every leaf is incident to at least one edge of $F$ – otherwise the parent of this leaf would witness the existence of a cut vertex in $G_{\cup }^{\prime }$ which is not possible. The tree $T$ has therefore at most $2\cdot \mathrm{fen}(G_{\cup })$ leaves and, consequently, at most $2\cdot \mathrm{fen}(G_{\cup })$ internal vertices of degree at least three. Let $C$ denote the set of vertices $v\in V(T)$ such that $v$ is of degree at least three in $T$ or we have $vu\in F$ for some $u\in G_{\cup }^{\prime }$. Observe that $C$ contains all leaves of $T$ and, since $|F|=\mathrm{fen}(G_{\cup })$, its size is in $𝒪(\mathrm{fen}(G_{\cup }))$. It remains to bound the number of vertices of degree 2 in $T$. We do that by bounding the length of a path in $T$ between a vertex $u\in C$ and its (first) ancestor $v\in C$ in $T$. Let $P$ be such a path. We observe that $P$ can have length at most 4. Otherwise, i.e., if $P$ consists of 5 or more vertices, there are at least 3 consecutive internal vertices that have degree 2 in $G_{\cup }^{\prime }$. These form a path whose endpoints are not connected in $G_{\cup }^{\prime }$. In particular, they form an ID2-path, a contradiction to the fact that we exhaustively applied the reduction rules of Kernel 1. As there are at most $𝒪(\mathrm{fen}(G_{\cup }))$ such paths, one for each vertex in $C$ (as $T$ is a tree), each of which is of constant length, $T$ (and thus $G_{\cup }$) consists of at most $𝒪(\mathrm{fen}(G_{\cup }))$ vertices. Moreover, as $T$ is a tree on $𝒪(\mathrm{fen}(G_{\cup }))$ vertices and $ℐ$ has the sunflower property, we have for each edge $e\in E(T)$ either $e\in E(G_{\cap }^{\prime })$ or $e\in E(G_i^{\prime })\setminus E(G_{\cap }^{\prime })$ for a single $i\in [k^{\prime }]$. As $T$ has $𝒪(\mathrm{fen}(G_{\cup }))$ edges, $|F|=\mathrm{fen}(G_{\cup })$, and since we delete input graphs whose edge set coincides with that of $G_{\cap }^{\prime }$, the number of remaining input graphs $k^{\prime }$ is in $𝒪(\mathrm{fen}(G_{\cup }))$. Finally, as S-SEFE is known to be in $\mathrm{𝖭𝖯}$ [32], it is decidable. With the safeness of the Rules I–III of Kernel 1 established in Lemmas 7, 8, and 9, the statement follows. $◀$

An $\mathrm{𝖥𝖯𝖳}$ (or $\mathrm{𝖷𝖯}$) algorithm parameterized by $cw(G_{\cup })+k$ yields an $\mathrm{𝖥𝖯𝖳}$ ($\mathrm{𝖷𝖯}$, respectively) algorithm parameterized by $tw(G_{\cup })+k$ due to the well-known fact that $\mathrm{cw}(G)\le 3\cdot 2^{\mathrm{tw}(G)-1}$ for every graph $G$ [20]. Conversely, assume we have an $\mathrm{𝖥𝖯𝖳}$ (or $\mathrm{𝖷𝖯}$) algorithm for (S-)SEFE parameterized by $\mathrm{tw}(G_{\cup })+k$. Consider an instance of (S-)SEFE parameterized by $cw(G_{\cup })+k$. If one of the input graphs is not planar, we can reject the instance. Otherwise, $k$ upper-bounds the thickness of $G_{\cup }$, i.e., the edges of $G_{\cup }$ can be partitioned into at most $k$ edge sets such that each edge set induces a planar graph on $G_{\cup }$.

It is known that for every graph of thickness $t^{\prime }$ there exists an integer $t$ which depends solely on the thickness of $G_{\cup }$ such that $G_{\cup }$ contains no $K_{t,t}$ as a subgraph [7]; notice here that $t$ depends solely on $k$. This in turn ensures that $\mathrm{tw}(G_{\cup })$ is upper-bounded by a function of $cw(G_{\cup })+t$ [34], and hence also by a function of $cw(G_{\cup })+k$. Therefore, the existing $\mathrm{𝖥𝖯𝖳}$ (or $\mathrm{𝖷𝖯}$) algorithm would imply fixed-parameter (or $\mathrm{𝖷𝖯}$, respectively) tractability of the problem w.r.t. $\mathrm{cw}(G_{\cup })+k$. $◀$

A different structural parameterization that has been successfully used for some other problems is graph degeneracy [17, 46, 8]. A graph $G$ is $d$-degenerate if every subgraph of G contains a vertex of degree at most $d$. The degeneracy of $G$ is then the smallest $d$ such that $G$ is $d$-degenerate. Here, we provide a straightforward argument that rules out any parameterized algorithms w.r.t. graph degeneracy.

We recall that SEFE and S-SEFE are known to remain $\mathrm{𝖭𝖯}$-hard when restricted to instances satisfying $k\le 3$ and, in particular, even $k=3$. For each instance $ℐ=(G_1,G_2,G_3)$ of (S-)SEFE, we construct a new instance ${ℐ}^{\prime }$ by subdividing every edge of each input graph once. Since $ℐ$ is a positive instance if and only if so is ${ℐ}^{\prime }$ but the union graph of every constructed instance has degeneracy $2$, the statement follows. $◀$

Finally, we believe that a promising target for future work would be to settle the parameterized complexity of S-SEFE w.r.t. to $k$ plus the twin-cover number [29, 30] (as has been asked in preceding work [26]) or $k$ plus the vertex integrity of the union graph [33, 47].