11institutetext:  Faculty of Informatics and Mathematics, University of
Passau, Germany 11email<EMAIL_ADDRESS>
# Parameterized Complexity of Simultaneous Planarity††thanks: Funded by the
Deutsche Forschungsgemeinschaft (German Research Foundation, DFG) under grant
RU-1903/3-1.

Simon D. Fink 11 0000-0002-2754-1195 Matthias Pfretzschner 11
0000-0002-5378-1694 Ignaz Rutter 11 0000-0002-3794-4406

###### Abstract

Given $k$ input graphs $G^{\leavevmode\hbox to5.89pt{\vbox
to5.89pt{\pgfpicture\makeatletter\hbox{\hskip 2.94316pt\lower-2.94316pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{2.74316pt}{0.0pt}\pgfsys@curveto{2.74316pt}{1.51501pt}{1.51501pt}{2.74316pt}{0.0pt}{2.74316pt}\pgfsys@curveto{-1.51501pt}{2.74316pt}{-2.74316pt}{1.51501pt}{-2.74316pt}{0.0pt}\pgfsys@curveto{-2.74316pt}{-1.51501pt}{-1.51501pt}{-2.74316pt}{0.0pt}{-2.74316pt}\pgfsys@curveto{1.51501pt}{-2.74316pt}{2.74316pt}{-1.51501pt}{2.74316pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.25pt}{-1.6111pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{\tiny$1$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}},\dots,G^{\leavevmode\hbox
to6.24pt{\vbox to6.24pt{\pgfpicture\makeatletter\hbox{\hskip
3.1204pt\lower-3.1204pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{2.92041pt}{0.0pt}\pgfsys@curveto{2.92041pt}{1.61292pt}{1.61292pt}{2.92041pt}{0.0pt}{2.92041pt}\pgfsys@curveto{-1.61292pt}{2.92041pt}{-2.92041pt}{1.61292pt}{-2.92041pt}{0.0pt}\pgfsys@curveto{-2.92041pt}{-1.61292pt}{-1.61292pt}{-2.92041pt}{0.0pt}{-2.92041pt}\pgfsys@curveto{1.61292pt}{-2.92041pt}{2.92041pt}{-1.61292pt}{2.92041pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.3802pt}{-1.7361pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{\tiny$k$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}$, where each pair
$G^{\leavevmode\hbox to5.47pt{\vbox
to5.47pt{\pgfpicture\makeatletter\hbox{\hskip 2.73491pt\lower-2.73491pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{2.53491pt}{0.0pt}\pgfsys@curveto{2.53491pt}{1.40001pt}{1.40001pt}{2.53491pt}{0.0pt}{2.53491pt}\pgfsys@curveto{-1.40001pt}{2.53491pt}{-2.53491pt}{1.40001pt}{-2.53491pt}{0.0pt}\pgfsys@curveto{-2.53491pt}{-1.40001pt}{-1.40001pt}{-2.53491pt}{0.0pt}{-2.53491pt}\pgfsys@curveto{1.40001pt}{-2.53491pt}{2.53491pt}{-1.40001pt}{2.53491pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-0.86128pt}{-1.6488pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{\tiny$i$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}$,
$G^{\leavevmode\hbox to6.65pt{\vbox
to6.65pt{\pgfpicture\makeatletter\hbox{\hskip 3.3228pt\lower-3.3228pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{3.1228pt}{0.0pt}\pgfsys@curveto{3.1228pt}{1.72469pt}{1.72469pt}{3.1228pt}{0.0pt}{3.1228pt}\pgfsys@curveto{-1.72469pt}{3.1228pt}{-3.1228pt}{1.72469pt}{-3.1228pt}{0.0pt}\pgfsys@curveto{-3.1228pt}{-1.72469pt}{-1.72469pt}{-3.1228pt}{0.0pt}{-3.1228pt}\pgfsys@curveto{1.72469pt}{-3.1228pt}{3.1228pt}{-1.72469pt}{3.1228pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.1726pt}{-1.1627pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{\tiny$j$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}$ with $i\neq j$
shares the same graph $G$, the problem Simultaneous Embedding With Fixed Edges
(SEFE) asks whether there exists a planar drawing for each input graph such
that all drawings coincide on $G$. While SEFE is still open for the case of
two input graphs, the problem is NP-complete for $k\geq 3$ [18].

In this work, we explore the parameterized complexity of SEFE. We show that
SEFE is FPT with respect to $k$ plus the vertex cover number or the feedback
edge set number of the union graph $G^{\cup}=G^{\leavevmode\hbox
to5.89pt{\vbox to5.89pt{\pgfpicture\makeatletter\hbox{\hskip
2.94316pt\lower-2.94316pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{2.74316pt}{0.0pt}\pgfsys@curveto{2.74316pt}{1.51501pt}{1.51501pt}{2.74316pt}{0.0pt}{2.74316pt}\pgfsys@curveto{-1.51501pt}{2.74316pt}{-2.74316pt}{1.51501pt}{-2.74316pt}{0.0pt}\pgfsys@curveto{-2.74316pt}{-1.51501pt}{-1.51501pt}{-2.74316pt}{0.0pt}{-2.74316pt}\pgfsys@curveto{1.51501pt}{-2.74316pt}{2.74316pt}{-1.51501pt}{2.74316pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.25pt}{-1.6111pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{\tiny$1$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}\cup\dots\cup
G^{\leavevmode\hbox to6.24pt{\vbox
to6.24pt{\pgfpicture\makeatletter\hbox{\hskip 3.1204pt\lower-3.1204pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{2.92041pt}{0.0pt}\pgfsys@curveto{2.92041pt}{1.61292pt}{1.61292pt}{2.92041pt}{0.0pt}{2.92041pt}\pgfsys@curveto{-1.61292pt}{2.92041pt}{-2.92041pt}{1.61292pt}{-2.92041pt}{0.0pt}\pgfsys@curveto{-2.92041pt}{-1.61292pt}{-1.61292pt}{-2.92041pt}{0.0pt}{-2.92041pt}\pgfsys@curveto{1.61292pt}{-2.92041pt}{2.92041pt}{-1.61292pt}{2.92041pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.3802pt}{-1.7361pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{\tiny$k$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}$. Regarding the
shared graph $G$, we show that SEFE is NP-complete, even if $G$ is a tree with
maximum degree 4. Together with a known NP-hardness reduction [1], this allows
us to conclude that several parameters of $G$, including the maximum degree,
the maximum number of degree-1 neighbors, the vertex cover number, and the
number of cutvertices are intractable. We also settle the tractability of all
pairs of these parameters. We give FPT algorithms for the vertex cover number
plus either of the first two parameters and for the number of cutvertices plus
the maximum degree, whereas we prove all remaining combinations to be
intractable.

##  1 Introduction

Let $G^{\leavevmode\hbox to5.89pt{\vbox
to5.89pt{\pgfpicture\makeatletter\hbox{\hskip 2.94316pt\lower-2.94316pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{2.74316pt}{0.0pt}\pgfsys@curveto{2.74316pt}{1.51501pt}{1.51501pt}{2.74316pt}{0.0pt}{2.74316pt}\pgfsys@curveto{-1.51501pt}{2.74316pt}{-2.74316pt}{1.51501pt}{-2.74316pt}{0.0pt}\pgfsys@curveto{-2.74316pt}{-1.51501pt}{-1.51501pt}{-2.74316pt}{0.0pt}{-2.74316pt}\pgfsys@curveto{1.51501pt}{-2.74316pt}{2.74316pt}{-1.51501pt}{2.74316pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.25pt}{-1.6111pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{\tiny$1$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}=(V,E^{\leavevmode\hbox
to5.89pt{\vbox to5.89pt{\pgfpicture\makeatletter\hbox{\hskip
2.94316pt\lower-2.94316pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{2.74316pt}{0.0pt}\pgfsys@curveto{2.74316pt}{1.51501pt}{1.51501pt}{2.74316pt}{0.0pt}{2.74316pt}\pgfsys@curveto{-1.51501pt}{2.74316pt}{-2.74316pt}{1.51501pt}{-2.74316pt}{0.0pt}\pgfsys@curveto{-2.74316pt}{-1.51501pt}{-1.51501pt}{-2.74316pt}{0.0pt}{-2.74316pt}\pgfsys@curveto{1.51501pt}{-2.74316pt}{2.74316pt}{-1.51501pt}{2.74316pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.25pt}{-1.6111pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{\tiny$1$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}})$, …,
$G^{\leavevmode\hbox to6.24pt{\vbox
to6.24pt{\pgfpicture\makeatletter\hbox{\hskip 3.1204pt\lower-3.1204pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{2.92041pt}{0.0pt}\pgfsys@curveto{2.92041pt}{1.61292pt}{1.61292pt}{2.92041pt}{0.0pt}{2.92041pt}\pgfsys@curveto{-1.61292pt}{2.92041pt}{-2.92041pt}{1.61292pt}{-2.92041pt}{0.0pt}\pgfsys@curveto{-2.92041pt}{-1.61292pt}{-1.61292pt}{-2.92041pt}{0.0pt}{-2.92041pt}\pgfsys@curveto{1.61292pt}{-2.92041pt}{2.92041pt}{-1.61292pt}{2.92041pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.3802pt}{-1.7361pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{\tiny$k$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}=(V,E^{\leavevmode\hbox
to6.24pt{\vbox to6.24pt{\pgfpicture\makeatletter\hbox{\hskip
3.1204pt\lower-3.1204pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{2.92041pt}{0.0pt}\pgfsys@curveto{2.92041pt}{1.61292pt}{1.61292pt}{2.92041pt}{0.0pt}{2.92041pt}\pgfsys@curveto{-1.61292pt}{2.92041pt}{-2.92041pt}{1.61292pt}{-2.92041pt}{0.0pt}\pgfsys@curveto{-2.92041pt}{-1.61292pt}{-1.61292pt}{-2.92041pt}{0.0pt}{-2.92041pt}\pgfsys@curveto{1.61292pt}{-2.92041pt}{2.92041pt}{-1.61292pt}{2.92041pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.3802pt}{-1.7361pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{\tiny$k$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}})$ denote $k$ graphs
on the same vertex set, where each pair $(G^{\leavevmode\hbox to5.47pt{\vbox
to5.47pt{\pgfpicture\makeatletter\hbox{\hskip 2.73491pt\lower-2.73491pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{2.53491pt}{0.0pt}\pgfsys@curveto{2.53491pt}{1.40001pt}{1.40001pt}{2.53491pt}{0.0pt}{2.53491pt}\pgfsys@curveto{-1.40001pt}{2.53491pt}{-2.53491pt}{1.40001pt}{-2.53491pt}{0.0pt}\pgfsys@curveto{-2.53491pt}{-1.40001pt}{-1.40001pt}{-2.53491pt}{0.0pt}{-2.53491pt}\pgfsys@curveto{1.40001pt}{-2.53491pt}{2.53491pt}{-1.40001pt}{2.53491pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-0.86128pt}{-1.6488pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{\tiny$i$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}},G^{\leavevmode\hbox
to6.65pt{\vbox to6.65pt{\pgfpicture\makeatletter\hbox{\hskip
3.3228pt\lower-3.3228pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{3.1228pt}{0.0pt}\pgfsys@curveto{3.1228pt}{1.72469pt}{1.72469pt}{3.1228pt}{0.0pt}{3.1228pt}\pgfsys@curveto{-1.72469pt}{3.1228pt}{-3.1228pt}{1.72469pt}{-3.1228pt}{0.0pt}\pgfsys@curveto{-3.1228pt}{-1.72469pt}{-1.72469pt}{-3.1228pt}{0.0pt}{-3.1228pt}\pgfsys@curveto{1.72469pt}{-3.1228pt}{3.1228pt}{-1.72469pt}{3.1228pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.1726pt}{-1.1627pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{\tiny$j$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}})$ has a common
_shared graph_ $G^{\leavevmode\hbox to5.47pt{\vbox
to5.47pt{\pgfpicture\makeatletter\hbox{\hskip 2.73491pt\lower-2.73491pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{2.53491pt}{0.0pt}\pgfsys@curveto{2.53491pt}{1.40001pt}{1.40001pt}{2.53491pt}{0.0pt}{2.53491pt}\pgfsys@curveto{-1.40001pt}{2.53491pt}{-2.53491pt}{1.40001pt}{-2.53491pt}{0.0pt}\pgfsys@curveto{-2.53491pt}{-1.40001pt}{-1.40001pt}{-2.53491pt}{0.0pt}{-2.53491pt}\pgfsys@curveto{1.40001pt}{-2.53491pt}{2.53491pt}{-1.40001pt}{2.53491pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-0.86128pt}{-1.6488pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{\tiny$i$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}\cap
G^{\leavevmode\hbox to6.65pt{\vbox
to6.65pt{\pgfpicture\makeatletter\hbox{\hskip 3.3228pt\lower-3.3228pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{3.1228pt}{0.0pt}\pgfsys@curveto{3.1228pt}{1.72469pt}{1.72469pt}{3.1228pt}{0.0pt}{3.1228pt}\pgfsys@curveto{-1.72469pt}{3.1228pt}{-3.1228pt}{1.72469pt}{-3.1228pt}{0.0pt}\pgfsys@curveto{-3.1228pt}{-1.72469pt}{-1.72469pt}{-3.1228pt}{0.0pt}{-3.1228pt}\pgfsys@curveto{1.72469pt}{-3.1228pt}{3.1228pt}{-1.72469pt}{3.1228pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.1726pt}{-1.1627pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{\tiny$j$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}=(V,E^{\leavevmode\hbox
to5.47pt{\vbox to5.47pt{\pgfpicture\makeatletter\hbox{\hskip
2.73491pt\lower-2.73491pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{2.53491pt}{0.0pt}\pgfsys@curveto{2.53491pt}{1.40001pt}{1.40001pt}{2.53491pt}{0.0pt}{2.53491pt}\pgfsys@curveto{-1.40001pt}{2.53491pt}{-2.53491pt}{1.40001pt}{-2.53491pt}{0.0pt}\pgfsys@curveto{-2.53491pt}{-1.40001pt}{-1.40001pt}{-2.53491pt}{0.0pt}{-2.53491pt}\pgfsys@curveto{1.40001pt}{-2.53491pt}{2.53491pt}{-1.40001pt}{2.53491pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-0.86128pt}{-1.6488pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{\tiny$i$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}\cap
E^{\leavevmode\hbox to6.65pt{\vbox
to6.65pt{\pgfpicture\makeatletter\hbox{\hskip 3.3228pt\lower-3.3228pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{3.1228pt}{0.0pt}\pgfsys@curveto{3.1228pt}{1.72469pt}{1.72469pt}{3.1228pt}{0.0pt}{3.1228pt}\pgfsys@curveto{-1.72469pt}{3.1228pt}{-3.1228pt}{1.72469pt}{-3.1228pt}{0.0pt}\pgfsys@curveto{-3.1228pt}{-1.72469pt}{-1.72469pt}{-3.1228pt}{0.0pt}{-3.1228pt}\pgfsys@curveto{1.72469pt}{-3.1228pt}{3.1228pt}{-1.72469pt}{3.1228pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.1726pt}{-1.1627pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{\tiny$j$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}})$. The problem
Simultaneous Embedding With Fixed Edges (SEFE) asks whether there exist planar
drawings $\Gamma^{\leavevmode\hbox to5.89pt{\vbox
to5.89pt{\pgfpicture\makeatletter\hbox{\hskip 2.94316pt\lower-2.94316pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{2.74316pt}{0.0pt}\pgfsys@curveto{2.74316pt}{1.51501pt}{1.51501pt}{2.74316pt}{0.0pt}{2.74316pt}\pgfsys@curveto{-1.51501pt}{2.74316pt}{-2.74316pt}{1.51501pt}{-2.74316pt}{0.0pt}\pgfsys@curveto{-2.74316pt}{-1.51501pt}{-1.51501pt}{-2.74316pt}{0.0pt}{-2.74316pt}\pgfsys@curveto{1.51501pt}{-2.74316pt}{2.74316pt}{-1.51501pt}{2.74316pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.25pt}{-1.6111pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{\tiny$1$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}},\dots,\Gamma^{\leavevmode\hbox
to6.24pt{\vbox to6.24pt{\pgfpicture\makeatletter\hbox{\hskip
3.1204pt\lower-3.1204pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{2.92041pt}{0.0pt}\pgfsys@curveto{2.92041pt}{1.61292pt}{1.61292pt}{2.92041pt}{0.0pt}{2.92041pt}\pgfsys@curveto{-1.61292pt}{2.92041pt}{-2.92041pt}{1.61292pt}{-2.92041pt}{0.0pt}\pgfsys@curveto{-2.92041pt}{-1.61292pt}{-1.61292pt}{-2.92041pt}{0.0pt}{-2.92041pt}\pgfsys@curveto{1.61292pt}{-2.92041pt}{2.92041pt}{-1.61292pt}{2.92041pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.3802pt}{-1.7361pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{\tiny$k$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}$ of
$G^{\leavevmode\hbox to5.89pt{\vbox
to5.89pt{\pgfpicture\makeatletter\hbox{\hskip 2.94316pt\lower-2.94316pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{2.74316pt}{0.0pt}\pgfsys@curveto{2.74316pt}{1.51501pt}{1.51501pt}{2.74316pt}{0.0pt}{2.74316pt}\pgfsys@curveto{-1.51501pt}{2.74316pt}{-2.74316pt}{1.51501pt}{-2.74316pt}{0.0pt}\pgfsys@curveto{-2.74316pt}{-1.51501pt}{-1.51501pt}{-2.74316pt}{0.0pt}{-2.74316pt}\pgfsys@curveto{1.51501pt}{-2.74316pt}{2.74316pt}{-1.51501pt}{2.74316pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.25pt}{-1.6111pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{\tiny$1$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}},\dots,G^{\leavevmode\hbox
to6.24pt{\vbox to6.24pt{\pgfpicture\makeatletter\hbox{\hskip
3.1204pt\lower-3.1204pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{2.92041pt}{0.0pt}\pgfsys@curveto{2.92041pt}{1.61292pt}{1.61292pt}{2.92041pt}{0.0pt}{2.92041pt}\pgfsys@curveto{-1.61292pt}{2.92041pt}{-2.92041pt}{1.61292pt}{-2.92041pt}{0.0pt}\pgfsys@curveto{-2.92041pt}{-1.61292pt}{-1.61292pt}{-2.92041pt}{0.0pt}{-2.92041pt}\pgfsys@curveto{1.61292pt}{-2.92041pt}{2.92041pt}{-1.61292pt}{2.92041pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.3802pt}{-1.7361pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{\tiny$k$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}$, respectively, such
that each pair $\Gamma^{\leavevmode\hbox to5.47pt{\vbox
to5.47pt{\pgfpicture\makeatletter\hbox{\hskip 2.73491pt\lower-2.73491pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{2.53491pt}{0.0pt}\pgfsys@curveto{2.53491pt}{1.40001pt}{1.40001pt}{2.53491pt}{0.0pt}{2.53491pt}\pgfsys@curveto{-1.40001pt}{2.53491pt}{-2.53491pt}{1.40001pt}{-2.53491pt}{0.0pt}\pgfsys@curveto{-2.53491pt}{-1.40001pt}{-1.40001pt}{-2.53491pt}{0.0pt}{-2.53491pt}\pgfsys@curveto{1.40001pt}{-2.53491pt}{2.53491pt}{-1.40001pt}{2.53491pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-0.86128pt}{-1.6488pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{\tiny$i$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}},\Gamma^{\leavevmode\hbox
to6.65pt{\vbox to6.65pt{\pgfpicture\makeatletter\hbox{\hskip
3.3228pt\lower-3.3228pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{3.1228pt}{0.0pt}\pgfsys@curveto{3.1228pt}{1.72469pt}{1.72469pt}{3.1228pt}{0.0pt}{3.1228pt}\pgfsys@curveto{-1.72469pt}{3.1228pt}{-3.1228pt}{1.72469pt}{-3.1228pt}{0.0pt}\pgfsys@curveto{-3.1228pt}{-1.72469pt}{-1.72469pt}{-3.1228pt}{0.0pt}{-3.1228pt}\pgfsys@curveto{1.72469pt}{-3.1228pt}{3.1228pt}{-1.72469pt}{3.1228pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.1726pt}{-1.1627pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{\tiny$j$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}$ induces the same
drawing on the shared graph $G^{\leavevmode\hbox to5.47pt{\vbox
to5.47pt{\pgfpicture\makeatletter\hbox{\hskip 2.73491pt\lower-2.73491pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{2.53491pt}{0.0pt}\pgfsys@curveto{2.53491pt}{1.40001pt}{1.40001pt}{2.53491pt}{0.0pt}{2.53491pt}\pgfsys@curveto{-1.40001pt}{2.53491pt}{-2.53491pt}{1.40001pt}{-2.53491pt}{0.0pt}\pgfsys@curveto{-2.53491pt}{-1.40001pt}{-1.40001pt}{-2.53491pt}{0.0pt}{-2.53491pt}\pgfsys@curveto{1.40001pt}{-2.53491pt}{2.53491pt}{-1.40001pt}{2.53491pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-0.86128pt}{-1.6488pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{\tiny$i$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}\cap
G^{\leavevmode\hbox to6.65pt{\vbox
to6.65pt{\pgfpicture\makeatletter\hbox{\hskip 3.3228pt\lower-3.3228pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{3.1228pt}{0.0pt}\pgfsys@curveto{3.1228pt}{1.72469pt}{1.72469pt}{3.1228pt}{0.0pt}{3.1228pt}\pgfsys@curveto{-1.72469pt}{3.1228pt}{-3.1228pt}{1.72469pt}{-3.1228pt}{0.0pt}\pgfsys@curveto{-3.1228pt}{-1.72469pt}{-1.72469pt}{-3.1228pt}{0.0pt}{-3.1228pt}\pgfsys@curveto{1.72469pt}{-3.1228pt}{3.1228pt}{-1.72469pt}{3.1228pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.1726pt}{-1.1627pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{\tiny$j$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}$ [10]. We refer to
such a $k$-tuple of drawings as a _simultaneous drawing_. Unless stated
otherwise, we assume that $k$ is part of the input and not necessarily a
constant. In this work, we focus on the restricted _sunflower case_ of SEFE,
where every pair of input graphs has the same shared graph $G$. For more than
two input graphs, SEFE has been proven to be NP-complete [13], even in the
sunflower case [18]. For two input graphs, however, SEFE remains open.

One of the main applications for the SEFE problem is dynamic graph drawing.
Given a graph that changes over time, a visualization of $k$ individual
snapshots of the graph should aesthetically display the changes between
successive snapshots. To this end, it is helpful to draw unchanged parts of
the graph consistently. Figure 1 gives an example illustrating this for $k=3$
snapshots. Using the same layout for the shared graph in Figure 1(b) notably
simplifies recognizing similarities and differences when compared to the
varying layouts in Figure 1(a).

(a)

(b)

Figure 1: (a) Three planar graphs $G^{\leavevmode\hbox to5.89pt{\vbox
to5.89pt{\pgfpicture\makeatletter\hbox{\hskip 2.94316pt\lower-2.94316pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{2.74316pt}{0.0pt}\pgfsys@curveto{2.74316pt}{1.51501pt}{1.51501pt}{2.74316pt}{0.0pt}{2.74316pt}\pgfsys@curveto{-1.51501pt}{2.74316pt}{-2.74316pt}{1.51501pt}{-2.74316pt}{0.0pt}\pgfsys@curveto{-2.74316pt}{-1.51501pt}{-1.51501pt}{-2.74316pt}{0.0pt}{-2.74316pt}\pgfsys@curveto{1.51501pt}{-2.74316pt}{2.74316pt}{-1.51501pt}{2.74316pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.25pt}{-1.6111pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{\tiny$1$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}$,
$G^{\leavevmode\hbox to5.89pt{\vbox
to5.89pt{\pgfpicture\makeatletter\hbox{\hskip 2.94316pt\lower-2.94316pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{2.74316pt}{0.0pt}\pgfsys@curveto{2.74316pt}{1.51501pt}{1.51501pt}{2.74316pt}{0.0pt}{2.74316pt}\pgfsys@curveto{-1.51501pt}{2.74316pt}{-2.74316pt}{1.51501pt}{-2.74316pt}{0.0pt}\pgfsys@curveto{-2.74316pt}{-1.51501pt}{-1.51501pt}{-2.74316pt}{0.0pt}{-2.74316pt}\pgfsys@curveto{1.51501pt}{-2.74316pt}{2.74316pt}{-1.51501pt}{2.74316pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.25pt}{-1.6111pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{\tiny$2$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}$, and
$G^{\leavevmode\hbox to5.89pt{\vbox
to5.89pt{\pgfpicture\makeatletter\hbox{\hskip 2.94316pt\lower-2.94316pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{2.74316pt}{0.0pt}\pgfsys@curveto{2.74316pt}{1.51501pt}{1.51501pt}{2.74316pt}{0.0pt}{2.74316pt}\pgfsys@curveto{-1.51501pt}{2.74316pt}{-2.74316pt}{1.51501pt}{-2.74316pt}{0.0pt}\pgfsys@curveto{-2.74316pt}{-1.51501pt}{-1.51501pt}{-2.74316pt}{0.0pt}{-2.74316pt}\pgfsys@curveto{1.51501pt}{-2.74316pt}{2.74316pt}{-1.51501pt}{2.74316pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.25pt}{-1.6111pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{\tiny$3$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}$ with the shared
graph $G$ highlighted in black. (b) Planar drawings of the same three graphs,
but the subgraph $G$ is drawn the same way in all three drawings.

In recent years, SEFE received much attention and many algorithms solving
restricted cases have been developed [17, 6]. Most notably, this includes the
cases where every connected component of $G$ is biconnected [5] or has a fixed
embedding [7], and the case where $G$ has maximum degree 3 [5]. Very recently,
Fulek and Tóth [12] solved SEFE for $k=2$ input graphs if the shared graph is
connected and Bläsius et al. [4] later improved the running time from
$O(n^{16})$ to quadratic using a reduction to the problem Synchronized
Planarity. For $k\geq 3$ input graphs, however, the same restricted case
remains NP-complete [1]. Despite the plethora of work dealing with SEFE in
restricted cases, we are not aware of parameterized approaches to SEFE.

In this work, we explore the parameterized complexity of SEFE. In Section 3,
we consider parameters of the _union graph_ $G^{\cup}=G^{\leavevmode\hbox
to5.89pt{\vbox to5.89pt{\pgfpicture\makeatletter\hbox{\hskip
2.94316pt\lower-2.94316pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{2.74316pt}{0.0pt}\pgfsys@curveto{2.74316pt}{1.51501pt}{1.51501pt}{2.74316pt}{0.0pt}{2.74316pt}\pgfsys@curveto{-1.51501pt}{2.74316pt}{-2.74316pt}{1.51501pt}{-2.74316pt}{0.0pt}\pgfsys@curveto{-2.74316pt}{-1.51501pt}{-1.51501pt}{-2.74316pt}{0.0pt}{-2.74316pt}\pgfsys@curveto{1.51501pt}{-2.74316pt}{2.74316pt}{-1.51501pt}{2.74316pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.25pt}{-1.6111pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{\tiny$1$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}\cup\dots\cup
G^{\leavevmode\hbox to6.24pt{\vbox
to6.24pt{\pgfpicture\makeatletter\hbox{\hskip 3.1204pt\lower-3.1204pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{2.92041pt}{0.0pt}\pgfsys@curveto{2.92041pt}{1.61292pt}{1.61292pt}{2.92041pt}{0.0pt}{2.92041pt}\pgfsys@curveto{-1.61292pt}{2.92041pt}{-2.92041pt}{1.61292pt}{-2.92041pt}{0.0pt}\pgfsys@curveto{-2.92041pt}{-1.61292pt}{-1.61292pt}{-2.92041pt}{0.0pt}{-2.92041pt}\pgfsys@curveto{1.61292pt}{-2.92041pt}{2.92041pt}{-1.61292pt}{2.92041pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.3802pt}{-1.7361pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{\tiny$k$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}$. We show that SEFE
is FPT with respect to $k$ plus the vertex cover number or the feedback edge
set number of $G^{\cup}$. Additionally, we prove intractability for SEFE
parameterized by the twin cover number of $G^{\cup}$. In Section 4, we turn to
parameters of the shared graph $G$. We consider as parameters the vertex cover
number $\operatorname{vc}(G)$, the feedback edge set number
$\operatorname{fes}(G)$, the number of connected components
$\operatorname{cc}(G)$, the number of cutvertices $\operatorname{cv}(G)$, the
maximum number of degree-1 neighbors $\Delta_{1}$ in $G$, the maximum degree
$\Delta$ of $G$, the maximum degree $\Delta^{\leavevmode\hbox to5.47pt{\vbox
to5.47pt{\pgfpicture\makeatletter\hbox{\hskip 2.73491pt\lower-2.73491pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{2.53491pt}{0.0pt}\pgfsys@curveto{2.53491pt}{1.40001pt}{1.40001pt}{2.53491pt}{0.0pt}{2.53491pt}\pgfsys@curveto{-1.40001pt}{2.53491pt}{-2.53491pt}{1.40001pt}{-2.53491pt}{0.0pt}\pgfsys@curveto{-2.53491pt}{-1.40001pt}{-1.40001pt}{-2.53491pt}{0.0pt}{-2.53491pt}\pgfsys@curveto{1.40001pt}{-2.53491pt}{2.53491pt}{-1.40001pt}{2.53491pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-0.86128pt}{-1.6488pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{\tiny$i$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}$ among all input
graphs, and the maximum degree $\Delta^{\cup}$ of the union graph. For the
latter four parameters, note that
$\Delta_{1}\leq\Delta\leq\Delta^{\leavevmode\hbox to5.47pt{\vbox
to5.47pt{\pgfpicture\makeatletter\hbox{\hskip 2.73491pt\lower-2.73491pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{2.53491pt}{0.0pt}\pgfsys@curveto{2.53491pt}{1.40001pt}{1.40001pt}{2.53491pt}{0.0pt}{2.53491pt}\pgfsys@curveto{-1.40001pt}{2.53491pt}{-2.53491pt}{1.40001pt}{-2.53491pt}{0.0pt}\pgfsys@curveto{-2.53491pt}{-1.40001pt}{-1.40001pt}{-2.53491pt}{0.0pt}{-2.53491pt}\pgfsys@curveto{1.40001pt}{-2.53491pt}{2.53491pt}{-1.40001pt}{2.53491pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-0.86128pt}{-1.6488pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{\tiny$i$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}\leq\Delta^{\cup}$.
Figure 2 gives an overview over these parameters together with their
individual and pairwise tractabilities. In Section 4.1, we show that SEFE is
NP-complete even if the shared graph is a tree with maximum degree 4. This
allows us to conclude that most parameters and their combinations are
intractable. The only exceptions are due to the FPT-algorithms from Section
4.2 for $\operatorname{vc}(G)+\Delta_{1}$ and from Section 4.3 for
$\operatorname{cv}(G)+\Delta$. Due to space constraints, proofs for statements
marked with a star are deferred to the full version [11].

Theorem 4.1
---
Theorem 4.2
Theorem 4.4
Theorem 4.5
Theorem 4.6

Figure 2: Complexity of SEFE parameterized by combinations of the parameters
of Section 4, assuming that the number of input graphs $k$ is part of the
input. Check marks indicate tractability and crosses indicate para-NP-
hardness. If $k$ is fixed, then Theorem 4.4 does not imply hardness, as the
reduction requires an unbounded number of input graphs; the corresponding
cells of the table are therefore still open. All other results also hold in
this case.

##  2 Preliminaries

For $k\in\mathbb{N}$, we define $[k]\coloneqq\\{1,\dots,k\\}$. Let $G=(V,E)$
be a simple graph. The _open neighborhood_ $N_{G}(v)$ of a vertex $v\in V$
denotes the set of vertices adjacent to $v$ in $G$. The _closed neighborhood_
$N_{G}[v]\coloneqq N_{G}(v)\cup\\{v\\}$ additionally contains $v$. If the
graph is clear from context, we simply write $N(v)$ and $N[v]$, respectively.
An _induced subgraph_ $H=(V^{\prime},E^{\prime})$ of $G$ contains all edges
$E^{\prime}\subseteq E$ with both endpoints in a given set
$V^{\prime}\subseteq V$. The graph $G$ is _connected_ , if, for every pair
$u,v\in V$, there exists a path between $u$ and $v$ in $G$. A _separating
$k$-set_ is a set $S\subseteq V$ with $|S|=k$ such that the graph $G-S$
obtained by removing $S$ is disconnected. The _split components_ of a
separating $k$-set $S$ are the maximal subgraphs of $G$ that are not
disconnected by removing $S$. A separating $1$-set is also called a
_cutvertex_ , a separating $2$-set is a _separating pair_. We say that $G$ is
_biconnected_ if it contains no cutvertex and _triconnected_ if it contains no
separating pair. A maximal induced subgraph of $G$ that is (bi-)connected is
called a _(bi-)connected component_ of $G$. A biconnected component is also
called a _block_. A _wheel_ is a graph that consists of a cycle and an
additional vertex adjacent to every vertex of the cycle.

Parameterized Complexity. A parameterized problem
$L\subseteq\Sigma^{*}\times\mathbb{N}$ is _fixed-parameter tractable (FPT)_ ,
if $L$ can be solved in time $f(k)\cdot n^{O(1)}$, where $f$ is some
computable function and $k$ is the parameter. The problem $L$ is _para-NP-
hard_ with respect to $k$ if $L$ is NP-hard even for constant values of $k$.
For a graph $G=(V,E)$, a _vertex cover_ is a vertex set $C\subseteq V$ such
that every edge $e\in E$ is incident to a vertex in $C$. The _vertex cover
number_ $\operatorname{vc}(G)$ is the size of a minimum vertex cover of $G$.
The following lemma states that the vertex cover number of a planar graph
gives an upper bound for the number of its high-degree vertices.

######  Lemma 1 ($\star$)

Let $G=(V,E)$ be a planar graph and let $N_{3}\subseteq V$ denote the set of
vertices of degree at least 3 in $G$. Then $|N_{3}|\leq
3\cdot\operatorname{vc}(G)$.

An edge $\\{u,v\\}\in E$ is a _twin edge_ if $N[u]=N[v]$, that is, $u$ and $v$
have the same neighborhood. A set $C\subseteq V$ is a _twin cover_ of $G$ if
every edge $e\in E$ is a twin edge or incident to a vertex of $C$. The _twin
cover number_ of $G$ is the size of a minimum twin cover of $G$. A _feedback
edge set_ of $G$ is an edge set $F\subseteq E$ such that $G-F$ is acyclic. The
_feedback edge set number_ $\operatorname{fes}(G)$ is the minimum size of a
feedback edge set of $G$.

SEFE. The graph $G^{\cup}=(V,\bigcup_{i\in[k]}E^{\leavevmode\hbox
to5.47pt{\vbox to5.47pt{\pgfpicture\makeatletter\hbox{\hskip
2.73491pt\lower-2.73491pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{2.53491pt}{0.0pt}\pgfsys@curveto{2.53491pt}{1.40001pt}{1.40001pt}{2.53491pt}{0.0pt}{2.53491pt}\pgfsys@curveto{-1.40001pt}{2.53491pt}{-2.53491pt}{1.40001pt}{-2.53491pt}{0.0pt}\pgfsys@curveto{-2.53491pt}{-1.40001pt}{-1.40001pt}{-2.53491pt}{0.0pt}{-2.53491pt}\pgfsys@curveto{1.40001pt}{-2.53491pt}{2.53491pt}{-1.40001pt}{2.53491pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-0.86128pt}{-1.6488pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{\tiny$i$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}})$ consisting of the
edges of all input graphs is called the _union graph_. For brevity, we
describe instances of SEFE using the union graph by marking every edge of
$G^{\cup}$ with the input graphs it is contained in. Every edge of $G^{\cup}$
is either contained in exactly one input graph $G^{\leavevmode\hbox
to5.47pt{\vbox to5.47pt{\pgfpicture\makeatletter\hbox{\hskip
2.73491pt\lower-2.73491pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{2.53491pt}{0.0pt}\pgfsys@curveto{2.53491pt}{1.40001pt}{1.40001pt}{2.53491pt}{0.0pt}{2.53491pt}\pgfsys@curveto{-1.40001pt}{2.53491pt}{-2.53491pt}{1.40001pt}{-2.53491pt}{0.0pt}\pgfsys@curveto{-2.53491pt}{-1.40001pt}{-1.40001pt}{-2.53491pt}{0.0pt}{-2.53491pt}\pgfsys@curveto{1.40001pt}{-2.53491pt}{2.53491pt}{-1.40001pt}{2.53491pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-0.86128pt}{-1.6488pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{\tiny$i$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}$, or in all of them.
In the former case, we say that the edge is _$i$ -exclusive_, in the latter
case it is _shared_. The connected components of the shared graph are also
called _shared components_.

Jünger and Schulz [14] showed that an instance of SEFE admits a simultaneous
embedding if and only if there exist embeddings of the input graphs that are
_compatible_ , i.e., they satisfy the following two requirements: (1) The
cyclic ordering of the edges around every vertex of $G$ must be identical in
all embeddings. (2) For every pair $C$ and $C^{\prime}$ of connected
components in $G$, the face of $C$ that $C^{\prime}$ is embedded in must be
the same in all embeddings. We call the former property _consistent edge
orderings_ and the latter property _consistent relative positions_ [17]. Note
that any SEFE instance with a non-planar input graph is a no-instance, we thus
assume all input graphs to be planar. Furthermore, Bläsius et al. [5] showed
that one can assume that the union graph is biconnected.

##  3 Parameters of the Union Graph

In this section, we study the parameters vertex cover number, feedback edge
set number, and twin cover number of the union graph
$G^{\cup}=G^{\leavevmode\hbox to5.89pt{\vbox
to5.89pt{\pgfpicture\makeatletter\hbox{\hskip 2.94316pt\lower-2.94316pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{2.74316pt}{0.0pt}\pgfsys@curveto{2.74316pt}{1.51501pt}{1.51501pt}{2.74316pt}{0.0pt}{2.74316pt}\pgfsys@curveto{-1.51501pt}{2.74316pt}{-2.74316pt}{1.51501pt}{-2.74316pt}{0.0pt}\pgfsys@curveto{-2.74316pt}{-1.51501pt}{-1.51501pt}{-2.74316pt}{0.0pt}{-2.74316pt}\pgfsys@curveto{1.51501pt}{-2.74316pt}{2.74316pt}{-1.51501pt}{2.74316pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.25pt}{-1.6111pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{\tiny$1$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}\cup\dots\cup
G^{\leavevmode\hbox to6.24pt{\vbox
to6.24pt{\pgfpicture\makeatletter\hbox{\hskip 3.1204pt\lower-3.1204pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{2.92041pt}{0.0pt}\pgfsys@curveto{2.92041pt}{1.61292pt}{1.61292pt}{2.92041pt}{0.0pt}{2.92041pt}\pgfsys@curveto{-1.61292pt}{2.92041pt}{-2.92041pt}{1.61292pt}{-2.92041pt}{0.0pt}\pgfsys@curveto{-2.92041pt}{-1.61292pt}{-1.61292pt}{-2.92041pt}{0.0pt}{-2.92041pt}\pgfsys@curveto{1.61292pt}{-2.92041pt}{2.92041pt}{-1.61292pt}{2.92041pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.3802pt}{-1.7361pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{\tiny$k$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}$. We give an FPT
algorithm for each of the former two in combination with $k$ and show the
latter to be intractable.

###  3.1 Vertex Cover Number

For our first parameterization, we consider the vertex cover number of the
union graph $\operatorname{vc}(G^{\cup})$. We use a similar approach as Bhore
et al. [2] in their parameterization of the problem Book Thickness. Let $C$ be
a minimum vertex cover of $G^{\cup}$ of size
$\varphi\coloneq\operatorname{vc}(G^{\cup})$ and let $k$ be the number of
input graphs. For every vertex $v\in V\setminus C$, note that
$N_{G^{\cup}}(v)\subseteq C$, as otherwise there would be an edge in
$G^{\cup}$ not covered by $C$. We group the vertices of $V(G^{\cup})\setminus
C$ into _types_ based on their neighborhood in all input graphs, i.e., two
vertices $v_{1}$ and $v_{2}$ are of the same type if and only if
$N_{G^{\leavevmode\hbox to5.47pt{\vbox
to5.47pt{\pgfpicture\makeatletter\hbox{\hskip 2.73491pt\lower-2.73491pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{2.53491pt}{0.0pt}\pgfsys@curveto{2.53491pt}{1.40001pt}{1.40001pt}{2.53491pt}{0.0pt}{2.53491pt}\pgfsys@curveto{-1.40001pt}{2.53491pt}{-2.53491pt}{1.40001pt}{-2.53491pt}{0.0pt}\pgfsys@curveto{-2.53491pt}{-1.40001pt}{-1.40001pt}{-2.53491pt}{0.0pt}{-2.53491pt}\pgfsys@curveto{1.40001pt}{-2.53491pt}{2.53491pt}{-1.40001pt}{2.53491pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-0.86128pt}{-1.6488pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{\tiny$i$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}(v_{1})=N_{G^{\leavevmode\hbox
to5.47pt{\vbox to5.47pt{\pgfpicture\makeatletter\hbox{\hskip
2.73491pt\lower-2.73491pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{2.53491pt}{0.0pt}\pgfsys@curveto{2.53491pt}{1.40001pt}{1.40001pt}{2.53491pt}{0.0pt}{2.53491pt}\pgfsys@curveto{-1.40001pt}{2.53491pt}{-2.53491pt}{1.40001pt}{-2.53491pt}{0.0pt}\pgfsys@curveto{-2.53491pt}{-1.40001pt}{-1.40001pt}{-2.53491pt}{0.0pt}{-2.53491pt}\pgfsys@curveto{1.40001pt}{-2.53491pt}{2.53491pt}{-1.40001pt}{2.53491pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-0.86128pt}{-1.6488pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{\tiny$i$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}(v_{2})$ for all
$i\in[k]$; see Figure 3. Let $\mathcal{P}$ denote the partition of $V\setminus
C$ based on the types of vertices. Let $\mathcal{P}_{\geq 3}\subseteq P$ be
the types of $\mathcal{P}$ whose vertices have degree at least 3 in some input
graph $G^{\leavevmode\hbox to5.47pt{\vbox
to5.47pt{\pgfpicture\makeatletter\hbox{\hskip 2.73491pt\lower-2.73491pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{2.53491pt}{0.0pt}\pgfsys@curveto{2.53491pt}{1.40001pt}{1.40001pt}{2.53491pt}{0.0pt}{2.53491pt}\pgfsys@curveto{-1.40001pt}{2.53491pt}{-2.53491pt}{1.40001pt}{-2.53491pt}{0.0pt}\pgfsys@curveto{-2.53491pt}{-1.40001pt}{-1.40001pt}{-2.53491pt}{0.0pt}{-2.53491pt}\pgfsys@curveto{1.40001pt}{-2.53491pt}{2.53491pt}{-1.40001pt}{2.53491pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-0.86128pt}{-1.6488pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{\tiny$i$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}$ and let
$\mathcal{P}_{\leq 2}\coloneq\mathcal{P}\setminus\mathcal{P}_{\geq 3}$ denote
the remaining types that have degree at most 2 in every input graph. Our first
goal is to bound the number of vertices in $\mathcal{P}_{\geq 3}$. Since every
input graph $G^{\leavevmode\hbox to5.47pt{\vbox
to5.47pt{\pgfpicture\makeatletter\hbox{\hskip 2.73491pt\lower-2.73491pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{2.53491pt}{0.0pt}\pgfsys@curveto{2.53491pt}{1.40001pt}{1.40001pt}{2.53491pt}{0.0pt}{2.53491pt}\pgfsys@curveto{-1.40001pt}{2.53491pt}{-2.53491pt}{1.40001pt}{-2.53491pt}{0.0pt}\pgfsys@curveto{-2.53491pt}{-1.40001pt}{-1.40001pt}{-2.53491pt}{0.0pt}{-2.53491pt}\pgfsys@curveto{1.40001pt}{-2.53491pt}{2.53491pt}{-1.40001pt}{2.53491pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-0.86128pt}{-1.6488pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{\tiny$i$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}$ is planar, we can
use Lemma 1 to bound the number of vertices of degree at least 3 in
$G^{\leavevmode\hbox to5.47pt{\vbox
to5.47pt{\pgfpicture\makeatletter\hbox{\hskip 2.73491pt\lower-2.73491pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{2.53491pt}{0.0pt}\pgfsys@curveto{2.53491pt}{1.40001pt}{1.40001pt}{2.53491pt}{0.0pt}{2.53491pt}\pgfsys@curveto{-1.40001pt}{2.53491pt}{-2.53491pt}{1.40001pt}{-2.53491pt}{0.0pt}\pgfsys@curveto{-2.53491pt}{-1.40001pt}{-1.40001pt}{-2.53491pt}{0.0pt}{-2.53491pt}\pgfsys@curveto{1.40001pt}{-2.53491pt}{2.53491pt}{-1.40001pt}{2.53491pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-0.86128pt}{-1.6488pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{\tiny$i$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}$ linearly in
$\operatorname{vc}(G^{\leavevmode\hbox to5.47pt{\vbox
to5.47pt{\pgfpicture\makeatletter\hbox{\hskip 2.73491pt\lower-2.73491pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{2.53491pt}{0.0pt}\pgfsys@curveto{2.53491pt}{1.40001pt}{1.40001pt}{2.53491pt}{0.0pt}{2.53491pt}\pgfsys@curveto{-1.40001pt}{2.53491pt}{-2.53491pt}{1.40001pt}{-2.53491pt}{0.0pt}\pgfsys@curveto{-2.53491pt}{-1.40001pt}{-1.40001pt}{-2.53491pt}{0.0pt}{-2.53491pt}\pgfsys@curveto{1.40001pt}{-2.53491pt}{2.53491pt}{-1.40001pt}{2.53491pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-0.86128pt}{-1.6488pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{\tiny$i$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}})\leq\varphi$. The
union graph $G^{\cup}$ can therefore only contain $O(k\varphi)$ vertices that
have degree at least 3 in some exclusive graph. Consequently, we obtain the
upper bound $|\bigcup\mathcal{P}_{\geq 3}|\in O(k\varphi)$.

(a)

(b)

Figure 3: (a) Vertices $u$ and $v$ of different types having different
neighborhoods in the two input graphs. $G^{\leavevmode\hbox to5.89pt{\vbox
to5.89pt{\pgfpicture\makeatletter\hbox{\hskip 2.94316pt\lower-2.94316pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{2.74316pt}{0.0pt}\pgfsys@curveto{2.74316pt}{1.51501pt}{1.51501pt}{2.74316pt}{0.0pt}{2.74316pt}\pgfsys@curveto{-1.51501pt}{2.74316pt}{-2.74316pt}{1.51501pt}{-2.74316pt}{0.0pt}\pgfsys@curveto{-2.74316pt}{-1.51501pt}{-1.51501pt}{-2.74316pt}{0.0pt}{-2.74316pt}\pgfsys@curveto{1.51501pt}{-2.74316pt}{2.74316pt}{-1.51501pt}{2.74316pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.25pt}{-1.6111pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{\tiny$1$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}$ is shown with thin
black edges, $G^{\leavevmode\hbox to5.89pt{\vbox
to5.89pt{\pgfpicture\makeatletter\hbox{\hskip 2.94316pt\lower-2.94316pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{2.74316pt}{0.0pt}\pgfsys@curveto{2.74316pt}{1.51501pt}{1.51501pt}{2.74316pt}{0.0pt}{2.74316pt}\pgfsys@curveto{-1.51501pt}{2.74316pt}{-2.74316pt}{1.51501pt}{-2.74316pt}{0.0pt}\pgfsys@curveto{-2.74316pt}{-1.51501pt}{-1.51501pt}{-2.74316pt}{0.0pt}{-2.74316pt}\pgfsys@curveto{1.51501pt}{-2.74316pt}{2.74316pt}{-1.51501pt}{2.74316pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.25pt}{-1.6111pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{\tiny$2$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}$ with thick blue
edges, overlapping edges belong to $G$. (b) Vertices $u$ and $v$ of the same
type.

It remains to bound the number of vertices contained in $\mathcal{P}_{\leq
2}$. Since these vertices have degree at most 2 in each input graph, there are
$O(\binom{\varphi}{2}^{k})$ distinct types in $\mathcal{P}_{\leq 2}$, i.e.,
$|\mathcal{P}_{\leq 2}|\in O(\varphi^{2k})$. To bound the number of vertices
of each type in $\mathcal{P}_{\leq 2}$, we use the following reduction rule;
see Figure 4.

Figure 4: An example illustrating the proof of Reduction Rule 1 for $k=2$
input graphs with vertices $u,v$ belonging to the same type of
$\mathcal{P}_{\leq 2}$. Vertex $v$ can be placed directly next to vertex $u$
in the face $f$ that $u$ is contained in without introducing any crossings in
the input graphs.

######  Reduction Rule 1 ($\star$)

If there exists a type $U\in\mathcal{P}_{\leq 2}$ with $|U|>1$, pick an
arbitrary vertex $v\in U$ and reduce the instance to $(G^{\cup}-v,k)$.

After exhaustively applying Reduction Rule 1, each type of $\mathcal{P}_{\leq
2}$ contains at most one vertex. Because we have $|\mathcal{P}_{\leq 2}|\in
O(\varphi^{2k})$, we thus get $|\bigcup\mathcal{P}_{\leq 2}|\in
O(\varphi^{2k})$. Using the upper bound $|\bigcup\mathcal{P}_{\geq 3}|\in
O(k\varphi)$ from above, we finally obtain a kernel of size
$|V|=|\bigcup\mathcal{P}_{\geq 3}|+|\bigcup\mathcal{P}_{\leq 2}|+|C|\in
O(\varphi^{2k})$ that can be solved in FPT time by enumerating all subsets of
its vertices. Combined with the fact that a minimum vertex cover of size
$\varphi$ can be computed in time $O(1.2738^{\varphi}+\varphi n)$ [8], we
obtain the following result.

###### Theorem 3.1

SEFE is FPT with respect to the number of input graphs $k$ plus the vertex
cover number $\varphi$ of the union graph $G^{\cup}$ and admits an
$O(\varphi^{2k})$ kernel.

We note that this result also holds in the non-sunflower case of SEFE.

###  3.2 Feedback Edge Set Number

In this section, we consider the feedback edge set number
$\psi=\operatorname{fes}(G^{\cup})$ of the union graph. We build on ideas of
Binucci et al. [3] in their parameterization of the problem StoryPlan. Given a
minimum feedback edge set $F$ of $G^{\cup}$, our goal is to bound the number
of vertices of $H\coloneqq G^{\cup}-F$ using reduction rules. Since $F$ is
minimal and we can assume $G^{\cup}$ to be connected, $H$ must be a tree.

Recall that we can even assume the union graph $G^{\cup}$ to be biconnected
due to the preprocessing by Bläsius et al. [5]. Since the preprocessing simply
decomposes split components around cutvertices of the union graph into
independent instances, the feedback edge set number of the graph does not
increase. The biconnectivity of $G^{\cup}$ ensures that $G^{\cup}$ does not
contain degree-1 vertices and therefore any leaf of $H$ must be incident to an
edge of $F$ in $G^{\cup}$. This allows us to bound the number of leaves (and
consequently also the number of nodes of degree at least 3) of $H$ linearly in
$|F|=\psi$.

It thus only remains to limit the number of degree-2 vertices in $H$. We do
this using a reduction rule that contracts edges in long paths of degree-2
vertices in $G^{\cup}$. If such a path contains a shared edge or two exclusive
edges of the same type, we can shorten the path as outlined in Figure 5. With
this reduction rule, we find a linear kernel for SEFE.

(a)

(b)

Figure 5: Contraction of a shared (a) or a $1$-exclusive (b) edge $e$ in a
path of degree-2 vertices. Because the path contains an additional
$1$-exclusive edge $e^{\prime}$ in (b), the endpoints $x$ and $y$ of $e$ are
contained in different connected components of all other input graphs. The
$2$-exclusive edge $g$ can thus be rerouted as illustrated.

######  Theorem 3.2 ($\star$)

SEFE is FPT parameterized by the number of input graphs $k$ plus the feedback
edge set number $\psi$ of the union graph $G^{\cup}$ and admits a kernel of
size $O(k\psi)$.

###  3.3 Twin Cover Number

Finally, we show that SEFE is para-NP-hard with respect to the twin cover
number of the union graph $G^{\cup}$. To this end, we use the following
theorem.

###### Theorem 3.3

When $k$ is part of the input, SEFE is NP-complete, even if the union graph is
a complete graph.

###### Proof

We start with the instance $G^{\cup}$ obtained from the reduction by Angelini
et al. [1] where the shared graph is a star (the remaining structure of the
instance is irrelevant). For every edge $e$ of the complement graph of
$G^{\cup}$ (i.e., for every edge that is missing in $G^{\cup}$), create a new
input graph $G^{\leavevmode\hbox to4.98pt{\vbox
to4.98pt{\pgfpicture\makeatletter\hbox{\hskip 2.49028pt\lower-2.49028pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{2.29028pt}{0.0pt}\pgfsys@curveto{2.29028pt}{1.2649pt}{1.2649pt}{2.29028pt}{0.0pt}{2.29028pt}\pgfsys@curveto{-1.2649pt}{2.29028pt}{-2.29028pt}{1.2649pt}{-2.29028pt}{0.0pt}\pgfsys@curveto{-2.29028pt}{-1.2649pt}{-1.2649pt}{-2.29028pt}{0.0pt}{-2.29028pt}\pgfsys@curveto{1.2649pt}{-2.29028pt}{2.29028pt}{-1.2649pt}{2.29028pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.16406pt}{-1.07639pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{\tiny$e$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}$ and add $e$ to
$G^{\leavevmode\hbox to4.98pt{\vbox
to4.98pt{\pgfpicture\makeatletter\hbox{\hskip 2.49028pt\lower-2.49028pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{2.29028pt}{0.0pt}\pgfsys@curveto{2.29028pt}{1.2649pt}{1.2649pt}{2.29028pt}{0.0pt}{2.29028pt}\pgfsys@curveto{-1.2649pt}{2.29028pt}{-2.29028pt}{1.2649pt}{-2.29028pt}{0.0pt}\pgfsys@curveto{-2.29028pt}{-1.2649pt}{-1.2649pt}{-2.29028pt}{0.0pt}{-2.29028pt}\pgfsys@curveto{1.2649pt}{-2.29028pt}{2.29028pt}{-1.2649pt}{2.29028pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.16406pt}{-1.07639pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{\tiny$e$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}$. Note that
$G^{\leavevmode\hbox to4.98pt{\vbox
to4.98pt{\pgfpicture\makeatletter\hbox{\hskip 2.49028pt\lower-2.49028pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{2.29028pt}{0.0pt}\pgfsys@curveto{2.29028pt}{1.2649pt}{1.2649pt}{2.29028pt}{0.0pt}{2.29028pt}\pgfsys@curveto{-1.2649pt}{2.29028pt}{-2.29028pt}{1.2649pt}{-2.29028pt}{0.0pt}\pgfsys@curveto{-2.29028pt}{-1.2649pt}{-1.2649pt}{-2.29028pt}{0.0pt}{-2.29028pt}\pgfsys@curveto{1.2649pt}{-2.29028pt}{2.29028pt}{-1.2649pt}{2.29028pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.16406pt}{-1.07639pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{\tiny$e$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}$ only consists of
the shared star and the additional edge $e$. As this does not restrict the
rotation of the star, we thus obtain an equivalent instance.

Note that, if $G^{\cup}$ is a complete graph, all vertices have the same
neighborhood and thus every edge is a twin edge, and consequently $G^{\cup}$
has twin cover number 0.

###### Theorem 3.4

When $k$ is part of the input, SEFE is para-NP-hard with respect to the twin
cover number of $G^{\cup}$.

Recall that the FPT algorithms from Sections 3.1 and 3.2 also require the
number of input graphs $k$ as a parameter. In contrast, Theorem 3.4 only holds
for unbounded $k$, since the reduction requires many input graphs.

##  4 Parameters of the Shared Graph

We now consider parameters of the shared graph $G$. In this case, finding safe
reduction rules becomes significantly more involved. While we may assume that
the union graph is biconnected [5], even isolated vertices or vertices of
degree 1 of the shared graph may hold important information due to their
connectivity in the union graph as the following result of Angelini et al. [1]
shows.

######  Theorem 4.1 ([1])

SEFE is NP-complete for any fixed $k\geq 3$, even if $G$ is a star.

Since, for a star, the vertex cover number $\operatorname{vc}(G)$, the
feedback edge set number $\operatorname{fes}(G)$, the number of connected
components $\operatorname{cc}(G)$, and the number of cutvertices
$\operatorname{cv}(G)$ are all constant, Theorem 4.1 already implies para-NP-
hardness for each of these parameters and for all combinations of them; see
Figure 2. To obtain additional hardness results, one can take the instance
resulting from Theorem 4.1, duplicate every edge of the star, and subdivide
each of the new duplication edges once. Since these new edges can be drawn
directly next to their original version (or simply be removed from the
drawing, if one wants to argue the reverse direction), the resulting instance
is equivalent. In this instance, the parameter $\Delta_{1}$, the maximum
number of degree-1 vertices adjacent to a single vertex in $G$, is zero, and
the only cutvertex of $G$ is the center vertex, thus filling additional gaps
in Figure 2. We note that this construction increases $\operatorname{fes}(G)$
and $\operatorname{vc}(G)$.

###### Theorem 4.2

SEFE is NP-complete for any fixed $k\geq 3$, even if $\Delta_{1}=0$ and
$\operatorname{cv}(G)=cc(G)=1$.

In the remainder of this section, we focus on several degree-related
parameters for SEFE. In addition to $\Delta_{1}$, we consider the maximum
degree $\Delta$ of the shared graph, the highest maximum degree
$\Delta^{\leavevmode\hbox to5.47pt{\vbox
to5.47pt{\pgfpicture\makeatletter\hbox{\hskip 2.73491pt\lower-2.73491pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{2.53491pt}{0.0pt}\pgfsys@curveto{2.53491pt}{1.40001pt}{1.40001pt}{2.53491pt}{0.0pt}{2.53491pt}\pgfsys@curveto{-1.40001pt}{2.53491pt}{-2.53491pt}{1.40001pt}{-2.53491pt}{0.0pt}\pgfsys@curveto{-2.53491pt}{-1.40001pt}{-1.40001pt}{-2.53491pt}{0.0pt}{-2.53491pt}\pgfsys@curveto{1.40001pt}{-2.53491pt}{2.53491pt}{-1.40001pt}{2.53491pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-0.86128pt}{-1.6488pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{\tiny$i$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}$ among all input
graphs, and the maximum degree $\Delta^{\cup}$ of the union graph. Recall that
$\Delta_{1}\leq\Delta\leq\Delta^{\leavevmode\hbox to5.47pt{\vbox
to5.47pt{\pgfpicture\makeatletter\hbox{\hskip 2.73491pt\lower-2.73491pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{2.53491pt}{0.0pt}\pgfsys@curveto{2.53491pt}{1.40001pt}{1.40001pt}{2.53491pt}{0.0pt}{2.53491pt}\pgfsys@curveto{-1.40001pt}{2.53491pt}{-2.53491pt}{1.40001pt}{-2.53491pt}{0.0pt}\pgfsys@curveto{-2.53491pt}{-1.40001pt}{-1.40001pt}{-2.53491pt}{0.0pt}{-2.53491pt}\pgfsys@curveto{1.40001pt}{-2.53491pt}{2.53491pt}{-1.40001pt}{2.53491pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-0.86128pt}{-1.6488pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{\tiny$i$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}\leq\Delta^{\cup}$.
Theorems 4.1 and 4.2 do not prove hardness for the latter three parameters as
the shared graph has high degree. To close this gap, we show in Section 4.1
that SEFE is NP-complete, even if the shared graph is a tree and the union
graph has maximum degree 4. This proves the intractability of many
combinations of parameters; see Figure 2. Finally, we show that SEFE is FPT
when parameterized by $\operatorname{vc}(G)+\Delta_{1}$ and by
$\operatorname{cv}(G)+\Delta$ (Sections 4.2 and 4.3), which settles the
remaining entries of Figure 2.

###  4.1 Maximum Degree

In this section we show that SEFE is NP-complete, even if the instance has
bounded degree. Angelini et al. [1] reduce from the NP-complete [15] problem
Betweenness, which asks for a linear ordering of a ground set $X$, subject to
a set $\mathcal{T}$ of triplets over $X$, where each triplet requires an
element to appear between two other elements in the ordering. They use the
rotation of a star in the shared graph to encode the linear ordering in the
SEFE instance, while exclusive edges enforce the triplets. Since this approach
leads to a high-degree vertex, we use a different approach. We use small-
degree vertices in the shared graph to encode the ordering of every three-
element subset of $X$, while the input graphs ensure compatibility between
these orderings. This results in a shared graph with small maximum degree, but
the number of input graphs is not constant.

Figure 6: An example illustrating the reduction of Theorem 4.3 with
$X=\\{x_{1},x_{2},x_{3},x_{4}\\}$ and
$\mathcal{T}=\\{(x_{1},x_{2},x_{3}),(x_{1},x_{2},x_{4})\\}$. Shared edges are
drawn in black, every other color represents one input graph.

######  Theorem 4.3 ($\star$)

When $k$ is part of the input, SEFE is NP-complete, even if the shared graph
is connected and has maximum degree 4.

######  Proof (Proof Sketch)

Figure 6 illustrates the SEFE instance resulting from the reduction from
Betweenness. For every $\tau\in\binom{X}{3}$, we have a degree-4 vertex
$v^{\tau}$ in the shared graph adjacent to vertices representing the three
elements of $\tau$. The fourth neighbor $u^{\tau}$of $v^{\tau}$ acts as a
separator that allows us to interpret the circular order of the edges incident
to $v^{\tau}$ as a linear order of $\tau$. The embeddings of the shared graph
thus correspond to linear orderings of all three-element subsets of $X$.

It remains to ensure that we only allow linear orderings of these subsets that
can be extended to a common linear order of $X$. For every pair of three-
element subsets that share two elements $a$ and $b$, we add two exclusive
edges in a new input graph that ensure that $a$ and $b$ are ordered
consistently in the two subsets; see Figure 6. Since the three-element subsets
themselves guarantee transitivity, our SEFE instance thus represents exactly
the linear orderings of $X$. To encode the additional constraint of each
triplet in $\mathcal{T}$ into our SEFE instance, we simply fix the vertices of
the corresponding three-element subset in a rigid structure in the shared
graph (see triplet $(x_{1},x_{2},x_{3})$ in Figure 6 for an example). We can
show that the resulting SEFE instance is equivalent to the original
Betweenness instance and that its shared graph is connected and has maximum
degree 4.

This result can be further improved by eliminating all cycles of the shared
graph and bounding the maximum degree of the union graph; see Figure 7.

Figure 7: An example illustrating how the instance obtained from the reduction
of Theorem 4.3 can be modified such that each vertex has degree at most 4 in
the union graph (first step) and the shared graph is acyclic (second step).

######  Theorem 4.4 ($\star$)

When $k$ is part of the input, SEFE is NP-complete, even if the shared graph
is a tree and the union graph has maximum degree 4.

###  4.2 Vertex Cover Number + Maximum Degree-1 Neighbors

Let $\Delta_{1}$ denote the maximum number of degree-1 vertices adjacent to a
single vertex in $G$ and let $C$ denote a minimum vertex cover of $G$ with
size $\varphi=\operatorname{vc}(G)$. In this section, we show that SEFE is FPT
with respect to $\varphi+\Delta_{1}$.

Since the shared graph is planar, the number of vertices with degree at least
3 in $G$ is at most $3\varphi$ by Lemma 1. Because $\Delta_{1}$ bounds the
number of degree-1 neighbors of each vertex in $G$, only the number of
isolated vertices and degree-2 vertices in the shared graph remains unbounded.
Unfortunately, it is difficult to reduce either of these vertex types in the
general case. Instead, our goal is to enumerate all suitable embeddings of the
shared graph. The SPQR-tree is a data structure of linear size that compactly
describes all planar embeddings of a graph by identifying subgraphs which can
be flipped and groups of subgraphs that can be arbitrarily permuted [9, 16].
The former are described by so-called _R-nodes_ , the latter by _P-nodes_
consisting of two _pole_ vertices forming a separating pair, their individual
split components are the subgraphs that can be arbitrarily permuted; see
Figure 8(a). Given the parameter $\varphi+\Delta_{1}$, the only embedding
choices we cannot afford to brute-force involve the P-nodes of $G$. Consider a
set $U$ of at least three degree-2 vertices of $G$ that have the same
neighborhood $\\{u,v\\}$. Note that neither of the vertices in $U$ has to be
contained in the vertex cover $C$ of $G$ if both $u$ and $v$ are contained in
$C$, thus $|U|$ is not necessarily bounded by a function in
$\varphi+\Delta_{1}$. In the SPQR-tree of $G$, $u$ and $v$ are the poles of a
P-node $\mu$ with at least $|U|$ parallel subgraphs and we therefore cannot
afford to enumerate all permutations of $\mu$. We call such a P-node _two-
parallel_. Even if we fix the embedding of $\mu$, the number of faces incident
to its poles is not bounded, leaving too many embedding decisions if one of
the poles of $\mu$ is a cutvertex in $G$; see Figure 8(a).

(a)

(b)

Figure 8: (a) A two-parallel P-node $\mu$ with many possible embedding choices
at cutvertex $v$. (b) Three blocks $B_{1}$, $B_{2}$, and $B_{3}$ of the shared
graph sharing the same cutvertex $v$. Block $B_{2}$ is a binary block (faces
$f_{2}$ and $f_{3}$) with respect to $B_{1}$, while $B_{3}$ is a mutable block
that can be embedded in all faces.

To circumvent these issues, we show that we can limit the number of embedding
decisions involving two-parallel P-nodes of $G$ using connectivity information
of the union graph, allowing us to brute-force all suitable embeddings of each
shared component in FPT-time. Subsequently, we can determine whether
$G^{\cup}$ admits a SEFE with the given embeddings using the algorithm by
Bläsius and Rutter [7] that solves SEFE if every shared component has a fixed
embedding. In other words, we use the bounded search tree technique where the
branches of the search tree correspond to embedding decisions in the shared
graph. We first branch for all possible embeddings of the blocks in $G$, and
subsequently branch for all possible configurations of blocks around
cutvertices.

######  Theorem 4.5 ($\star$)

When $k$ is part of the input, SEFE is FPT with respect to the maximum number
of degree-1 neighbors $\Delta_{1}$ and the vertex cover number $\varphi$ of
the shared graph and can be solved in

${O(2^{O(\varphi)}\cdot(2(\varphi+\Delta_{1}))^{(\varphi+\Delta_{1})^{2}\cdot
3\varphi}\cdot((\varphi+\Delta_{1})!)^{3\varphi}\cdot n^{O(1)})}\
\text{time.}$

######  Proof (Proof Sketch)

We give a high-level overview of our strategy. For details, we refer to the
full version [11].

As the first step, we embed all blocks of the shared graph $G$. To this end,
we can use the preprocessing steps introduced by Bläsius et al. [5] which
essentially guarantee that every P-node of $G$ has a fixed embedding (up to
mirroring) due to connectivity information of the union graph and thus (as for
R-nodes) only leave a binary embedding choice. Subsequently, we show that the
number of P-nodes and R-nodes in $G$ is bounded linearly in $\varphi$. We can
therefore enumerate all suitable embeddings of all blocks in $G$ using
$O(2^{\varphi})$ branches.

Given a fixed embedding for all blocks of $G$, it remains to nest and order
the blocks around all cutvertices of $G$. Let $v$ be a cutvertex and let
$B_{1}$ and $B_{2}$ be two blocks of $G$ containing $v$. Again, preprocessing
steps by Bläsius et al. [5] and the connectivity of the union graph restrict
the faces of $B_{1}$ that $B_{2}$ can potentially be embedded in. If $B_{2}$
can be embedded in at most two faces of $B_{1}$, we say that $B_{2}$ is a
_binary block_ with respect to $B_{1}$, otherwise it is a _mutable block_ ;
see Figure 8(b). First, we branch for each possible assignment of binary
blocks to each of their respective admissible faces and subsequently call
every face with an assigned block _occupied_. This does not work for mutable
blocks as the number of faces they may be embedded in is not necessarily
bounded by our parameters. However, we show (roughly speaking) that we can
decide whether a mutable block is compatible with a given face $f$ using just
connectivity information of the union graph, as long as $f$ is not occupied.
If there exists a compatible face that is not occupied, we can assign the
block to that face without branching. Otherwise, we successively branch and
assign the block to each occupied face, the number of which is bounded by our
parameters.

With a fixed nesting of blocks at every cutvertex $v$ of $G$, it only remains
to order blocks that lie in the same face. Since $\varphi$ bounds the number
of vertices of degree at least 3 in $G$ (Lemma 1) and $\varphi+\Delta_{1}$
bounds the number of blocks in $G$, we can brute-force all such orderings. In
every branch of the search tree, we thus now have a fixed embedding for each
component of the shared graph $G$ and can solve the instance using the
algorithm by Bläsius and Rutter [7].

###  4.3 Number of Cutvertices + Maximum Degree

In this section, we consider the parameters number of cutvertices
$\operatorname{cv}(G)$ and maximum degree $\Delta$ of the shared graph $G$.
This combination enables us to brute-force all possible orders of incident
edges at cutvertices of $G$, thereby allowing us to effectively treat each
biconnected component separately. In the following, we give a brief outline of
this approach, details are given in the full version [11].

To solve instances where every connected component of the shared graph is
biconnected, Bläsius et al. [5] show that, for a biconnected planar graph $G$
and a set $X$ of vertices of $G$ that share a face in some planar embedding of
$G$, the order of $X$ along any simple cycle in $G$ is fixed up to reversal
[5, Lemma 8]. This essentially allows them to decompose the instance at such
cycles of the shared graph, as the “interface” the graph provides for the
vertices of $X$ is independent of the embedding. We show that the same holds
for facial cycles of non-biconnected planar graphs if every cutvertex $v$ has
a fixed rotation $\sigma_{v}$. We say that a walk $W$ (i.e., a connected
sequence of vertices) of $G$ is _face-embeddable_ if there exists a planar
embedding of $G$ where $W$ is a facial cycle.

######  Lemma 2 ($\star$)

Let $G$ be a planar graph where every cutvertex has a fixed rotation. Let $X$
be a set of vertices that are incident to a common face in some planar
embedding of $G$. Then the order of $X$ in any face-embeddable walk of $G$
containing $X$ is unique up to reversal.

Figure 9: Decomposing $G^{\cup}$ at a cutvertex $v$. The orange edges belong
to an extra input graph that enforces the fixed rotation of the cutvertices.

This allows us to decompose the instance $G^{\cup}$ at cutvertices of the
shared graph $G$; see Figure 9. We partition the vertices of $G-v$ into two
sets $V_{1}$ and $V_{2}$ such that the edges connecting each of the sets with
cutvertex $v$ are consecutive in $\sigma_{v}$ and no vertices belonging to the
same block of $G$ are separated. We remark that the choice of $V_{1}$ and
$V_{2}$ is in general not unique. Note that the fixed rotation $\sigma_{v}$
defines nestings of the split components in $V_{2}$. Given this information,
we (i) contract in $G^{\cup}$ each set of split components in $V_{2}$ that
belong to the same nesting (highlighted in red in Figure 9) into a single
vertex that is only connected to $v$ via exclusive edges and (ii) contract
every shared component contained in $V_{2}$ (highlighted in yellow in Figure
9) into a single vertex. This yields the graph $G^{\cup}_{1}$. The
construction ensures that all _attachment vertices_ of the split components in
$V_{1}$ that a split component in $V_{2}$ is connected to lie on the outer
face of the split components in any simultaneous embedding of $G^{\cup}_{1}$.
Symmetrically, we obtain graph $G^{\cup}_{2}$ by interchanging $V_{1}$ and
$V_{2}$.

To test whether $G^{\cup}$ admits a SEFE, we first test $G^{\cup}_{1}$ and
$G^{\cup}_{2}$. Note that both graphs contain fewer split components at $v$,
we thus make progress towards biconnectivity. If both graphs admit a SEFE (a
necessary condition), we merge their embeddings of the shared graph back
together at vertex $v$ and test whether $G^{\cup}$ admits a SEFE with this
fixed embedding of the shared graph using the algorithm by Bläsius and Rutter
[7]. This is necessary and sufficient as the order of the attachment vertices
on the outer face of the split components contained in $V_{1}$ (respectively
$V_{2}$) is the same in any embedding by Lemma 2. Thus, if $G^{\cup}$ admits a
simultaneous embedding, it also admits a simultaneous embedding where the
shared graph has our chosen embedding.

######  Theorem 4.6 ($\star$)

When $k$ is part of the input, SEFE is FPT with respect to the number of
cutvertices $\operatorname{cv}(G)$ and the maximum degree $\Delta$ of $G$ and
can be solved in $O((\Delta!)^{\operatorname{cv}(G)}\cdot n^{O(1)})$ time.

##  5 Conclusion

Our FPT algorithms for the vertex cover number (Section 3.1) and the feedback
edge set number (Section 3.2) of the union graph both additionally require the
number of input graphs $k$ as a parameter, raising the question whether
similar results can be obtained for unbounded $k$. In contrast, the reduction
showing para-NP-hardness of SEFE with respect to the twin cover number of the
union graph (Section 3.3) requires $k$ to be unbounded. Is the problem FPT
parameterized by the twin cover number plus $k$?

For the shared graph, we have shown that all eight parameters we considered
(and most of their combinations; see Figure 2) are intractable. This even
includes the vertex cover number, one of the strongest graph parameters that
upper bounds numerous other metrics like the feedback vertex set number, the
treedepth, the pathwidth, and the treewidth. Most of the intractabilities
regarding degree-related parameters follow from our hardness reduction for
SEFE with maximum degree 4 in Theorem 4.4. However, Theorem 4.4 only holds if
the number $k$ of input graphs is unbounded, as the reduction inherently
requires many input graphs. It is therefore an interesting question whether
these parameters become tractable when one additionally considers $k$ as a
parameter.

## References

  * [1] Angelini, P., Da Lozzo, G., Neuwirth, D.: Advancements on SEFE and partitioned book embedding problems. Theor. Comput. Sci. 575, 71–89 (2015). https://doi.org/10.1016/j.tcs.2014.11.016
  * [2] Bhore, S., Ganian, R., Montecchiani, F., Nöllenburg, M.: Parameterized algorithms for book embedding problems. J. Graph Algorithms Appl. 24(4), 603–620 (2020). https://doi.org/10.7155/jgaa.00526
  * [3] Binucci, C., Di Giacomo, E., Lenhart, W.J., Liotta, G., Montecchiani, F., Nöllenburg, M., Symvonis, A.: On the complexity of the storyplan problem. In: Angelini, P., von Hanxleden, R. (eds.) Proceedings of the 30th International Symposium on Graph Drawing (GD’22). Lecture Notes in Computer Science, vol. 13764, pp. 304–318. Springer (2022). https://doi.org/10.1007/978-3-031-22203-0_22
  * [4] Bläsius, T., Fink, S.D., Rutter, I.: Synchronized planarity with applications to constrained planarity problems. In: Mutzel, P., Pagh, R., Herman, G. (eds.) Proceedings of the 29th Annual European Symposium on Algorithms (ESA’21). LIPIcs, vol. 204, pp. 19:1–19:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021). https://doi.org/10.4230/LIPIcs.ESA.2021.19
  * [5] Bläsius, T., Karrer, A., Rutter, I.: Simultaneous embedding: Edge orderings, relative positions, cutvertices. Algorithmica 80(4), 1214–1277 (2018). https://doi.org/10.1007/s00453-017-0301-9
  * [6] Bläsius, T., Kobourov, S.G., Rutter, I.: Simultaneous embedding of planar graphs. In: Tamassia, R. (ed.) Handbook on Graph Drawing and Visualization, pp. 349–381. Chapman and Hall/CRC (2013)
  * [7] Bläsius, T., Rutter, I.: Disconnectivity and relative positions in simultaneous embeddings. Comput. Geom. 48(6), 459–478 (2015). https://doi.org/10.1016/j.comgeo.2015.02.002
  * [8] Chen, J., Kanj, I.A., Xia, G.: Improved upper bounds for vertex cover. Theor. Comput. Sci. 411(40-42), 3736–3756 (2010). https://doi.org/10.1016/j.tcs.2010.06.026
  * [9] Di Battista, G., Tamassia, R.: On-line maintenance of triconnected components with SPQR-trees. Algorithmica 15(4), 302–318 (1996). https://doi.org/10.1007/BF01961541
  * [10] Erten, C., Kobourov, S.G.: Simultaneous embedding of planar graphs with few bends. J. Graph Algorithms Appl. 9(3), 347–364 (2005). https://doi.org/10.7155/jgaa.00113
  * [11] Fink, S.D., Pfretzschner, M., Rutter, I.: Parameterized complexity of simultaneous planarity. CoRR abs/2308.11401 (2023). https://doi.org/10.48550/arXiv.2308.11401
  * [12] Fulek, R., Tóth, C.D.: Atomic embeddability, clustered planarity, and thickenability. In: Chawla, S. (ed.) Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, (SODA’20). pp. 2876–2895. SIAM (2020). https://doi.org/10.1137/1.9781611975994.175
  * [13] Gassner, E., Jünger, M., Percan, M., Schaefer, M., Schulz, M.: Simultaneous graph embeddings with fixed edges. In: Fomin, F.V. (ed.) Proceedings of the 32nd Workshop on Graph-Theoretic Concepts in Computer Science (WG’06). Lecture Notes in Computer Science, vol. 4271, pp. 325–335. Springer (2006). https://doi.org/10.1007/11917496_29
  * [14] Jünger, M., Schulz, M.: Intersection graphs in simultaneous embedding with fixed edges. J. Graph Algorithms Appl. 13(2), 205–218 (2009). https://doi.org/10.7155/jgaa.00184
  * [15] Opatrny, J.: Total ordering problem. SIAM J. Comput. 8(1), 111–114 (1979). https://doi.org/10.1137/0208008
  * [16] Patrignani, M.: Planarity testing and embedding. In: Tamassia, R. (ed.) Handbook on Graph Drawing and Visualization, pp. 1–42. Chapman and Hall/CRC (2013)
  * [17] Rutter, I.: Simultaneous embedding. In: Hong, S., Tokuyama, T. (eds.) Beyond Planar Graphs, Communications of NII Shonan Meetings, pp. 237–265. Springer (2020). https://doi.org/10.1007/978-981-15-6533-5_13
  * [18] Schaefer, M.: Toward a theory of planarity: Hanani-tutte and planarity variants. J. Graph Algorithms Appl. 17(4), 367–440 (2013). https://doi.org/10.7155/jgaa.00298