A Dichotomy for 1-Planarity with Restricted Crossing Types Parameterized by Treewidth

Cabello, Sergio; Dobler, Alexander; Fijavž, Gašper; Hamm, Thekla; Wagner, Mirko H.

doi:10.4230/LIPIcs.ISAAC.2025.16

A Dichotomy for 1-Planarity with Restricted Crossing Types Parameterized by Treewidth

Sergio Cabello

Faculty of Mathematics and Physics, University of Ljubljana, Slovenia
Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia Alexander Dobler

TU Wien, Austria Gašper Fijavž

Faculty of Computer and Information Science, University of Ljubljana, Slovenia Thekla Hamm

Department of Mathematics and Computer Science, TU Eindhoven, The Netherlands Mirko H. Wagner

Theoretical Computer Science, Osnabrück University, Germany

Abstract

A drawing of a graph is $1$ -planar if each edge participates in at most one crossing and adjacent edges do not cross. Up to symmetry, each crossing in a $1$ -planar drawing belongs to one out of six possible crossing types, where a type characterizes the subgraph induced by the four vertices of the crossing edges. Each of the $63$ possible nonempty subsets $\mathcal{S}$ of crossing types gives a recognition problem: does a given graph admit an $\mathcal{S}$ -restricted drawing, that is, a $1$ -planar drawing where the crossing type of each crossing is in $\mathcal{S}$ ?

We show that there is a set $\mathcal{S}_{\rm bad}$ with three crossing types and the following properties:

$\blacksquare$

If $\mathcal{S}$ contains no crossing type from $\mathcal{S}_{\rm bad}$ , then the recognition of graphs that admit an $\mathcal{S}$ -restricted drawing is fixed-parameter tractable with respect to the treewidth of the input graph.
$\blacksquare$

If $\mathcal{S}$ contains any crossing type from $\mathcal{S}_{\rm bad}$ , then it is NP-hard to decide whether a graph has an $\mathcal{S}$ -restricted drawing, even when considering graphs of constant pathwidth.

We also extend this characterization of crossing types to $1$ -planar straight-line drawings and show the same complexity behaviour parameterized by treewidth.

Keywords and phrases:

1-planar, crossing type, treewidth, pathwidth

Funding:

Sergio Cabello: Funded in part by the Slovenian Research and Innovation Agency (P1-0297, N1-0218, N1-0285). Funded in part by the European Union (ERC, KARST, project number 101071836). Views and opinions expressed are however those of the authors only and do not necessarily reflect those of the European Union or the European Research Council. Neither the European Union nor the granting authority can be held responsible for them.

Alexander Dobler: Vienna Science and Technology Fund (WWTF) grant [10.47379/ICT19035].

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Design and analysis of algorithms ; Theory of computation

\rightarrow

Fixed parameter tractability

Acknowledgements:

This work was started during the Crossing Number Workshop 2024 that took place in Montserrat, Spain. We thank the organizers and participants for providing a fruitful research environment.

DOI:

10.4230/LIPIcs.ISAAC.2025.16

Event:

36th International Symposium on Algorithms and Computation (ISAAC 2025)

Editors:

Ho-Lin Chen, Wing-Kai Hon, and Meng-Tsung Tsai

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

Drawings of graphs are encountered early and used often: children are challenged to draw $K_{3,3}$ without crossings, drawings of graphs are regularly used when teaching graphs, they appear in any graph-related textbook, and we use them in our research discussions. Drawings of graphs naturally led to the concept of planar graphs and, more generally, an interest to control the crossings in the drawings.

Planar graphs enjoy a rich structural theory, have spurred research in graph theory and graph algorithms, and are relatively well understood. However, they are a quite restrictive class of graphs, and non-planar graphs still have to be drawn. For this reason, a range of beyond-planarity concepts have been suggested and investigated [12, 21, 29]. In this work, we will focus on $1$ -planarity, one of the extensions of planarity that has attracted much interest [22]. A drawing of a graph is $1$ -planar (or has local crossing number $1$ ) if each edge participates in at most one crossing and adjacent edges do not cross¹¹1The condition of non-crossing adjacent edges is usually added because whenever the edges $u v$ and $uv^{\prime}$ cross in a drawing, we can get a drawing with fewer crossings by redrawing the start of the edges $uv,uv^{\prime}$ .. A graph is $1$ -planar iff it admits a $1$ -planar drawing.

Generally speaking, the class of $1$ -planar graphs is not well understood. We know that recognizing $1$ -planar graphs is computationally hard [16, 23], even for graphs that are obtained from a planar graph by adding a single edge [9], or for graphs with constant treewidth, pathwidth or even bandwidth [1]. A fixed-parameter algorithm for deciding the existence of $1$ -planar drawings has been obtained recently by Hamm and Hlinený [19] (and actually is an easy consequence of [17]) using the total number of crossings in the drawing as a parameter.

Biedl and Murali [4] noticed that the crossings in a $1$ -planar drawing can be classified into different types, and the (non-)existence of some types may have important consequences. We will call these different types crossing types, and they describe adjacencies between the endpoints of the edges involved in that crossing. Consequently, there are six different crossing types (up to symmetry), for which we follow the terminology from [4]: (1) A full crossing is one in which each endpoint of an edge involved in that crossing is connected to each other such endpoint (), (2) an almost full crossing is one in which all but one pair of endpoints of the edges involved in that crossing are connected to each other ( $\hbox to4.95pt{\vbox to4.95pt{\pgfpicture\makeatletter\hbox{\>\lower-2.4763pt% \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{\the% \pgflinewidth}\pgfsys@invoke{ }\nullfont\hbox to0.0pt{\pgfsys@beginscope% \pgfsys@invoke{ }{{}} {}{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ % }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{2.2763pt}\pgfsys@lineto{-2.2763pt}{-2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{-2.2763pt}\pgfsys@lineto{-2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope {{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{-2.2763pt}\pgfsys@lineto{2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{2.2763pt}\pgfsys@lineto{-2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{-2.2763pt}{2.2763pt}\pgfsys@lineto{-2.2763pt}{-2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope \pgfsys@invoke{ }\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{% }\pgfsys@endscope\hss}}\endpgfpicture}})$ , (3) a bowtie crossing is one in which the graph induced by the endpoints of the edges involved in that crossing is a $4$ -cycle (), (4) an arrow crossing is one in which there is precisely one endpoint of an edge involved in that crossing that is connected to all other such endpoints (), (5) a chair crossing is one in which all but one pair of endpoints of the edges involved in that crossing are independent if one were to remove the edges involved in the crossing () (6) a $\times$ crossing is one in which all endpoints of the edges involved in that crossing are independent if one were to remove the edges involved in the crossing ().

For each non-empty $\mathcal{S}\subseteq\{\hbox to4.95pt{\vbox to4.95pt{\pgfpicture\makeatletter% \hbox{\>\lower-2.4763pt\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{\the\pgflinewidth}\pgfsys@invoke{ }\nullfont\hbox to0.0pt% {\pgfsys@beginscope\pgfsys@invoke{ }{{}} {}{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ % }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{2.2763pt}\pgfsys@lineto{-2.2763pt}{-2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{-2.2763pt}\pgfsys@lineto{-2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{-2.2763pt}{-2.2763pt}\pgfsys@lineto{2.2763pt}{-2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{-2.2763pt}\pgfsys@lineto{2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{2.2763pt}\pgfsys@lineto{-2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{-2.2763pt}{2.2763pt}\pgfsys@lineto{-2.2763pt}{-2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope \pgfsys@invoke{ }\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{% }\pgfsys@endscope\hss}}\endpgfpicture}},\hbox to4.95pt{\vbox to4.95pt{% \pgfpicture\makeatletter\hbox{\>\lower-2.4763pt\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{\the\pgflinewidth}\pgfsys@invoke{ }% \nullfont\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}} {}{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ % }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{2.2763pt}\pgfsys@lineto{-2.2763pt}{-2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{-2.2763pt}\pgfsys@lineto{-2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope {{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{-2.2763pt}\pgfsys@lineto{2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{2.2763pt}\pgfsys@lineto{-2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{-2.2763pt}{2.2763pt}\pgfsys@lineto{-2.2763pt}{-2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope \pgfsys@invoke{ }\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{% }\pgfsys@endscope\hss}}\endpgfpicture}},\hbox to4.95pt{\vbox to4.95pt{% \pgfpicture\makeatletter\hbox{\>\lower-2.4763pt\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{\the\pgflinewidth}\pgfsys@invoke{ }% \nullfont\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}} {}{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ % }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{2.2763pt}\pgfsys@lineto{-2.2763pt}{-2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{-2.2763pt}\pgfsys@lineto{-2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope {{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{-2.2763pt}\pgfsys@lineto{2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope {{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{-2.2763pt}{2.2763pt}\pgfsys@lineto{-2.2763pt}{-2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope \pgfsys@invoke{ }\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{% }\pgfsys@endscope\hss}}\endpgfpicture}},\hbox to4.95pt{\vbox to4.95pt{% \pgfpicture\makeatletter\hbox{\>\lower-2.4763pt\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{\the\pgflinewidth}\pgfsys@invoke{ }% \nullfont\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}} {}{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ % }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{2.2763pt}\pgfsys@lineto{-2.2763pt}{-2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{-2.2763pt}\pgfsys@lineto{-2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{-2.2763pt}{-2.2763pt}\pgfsys@lineto{2.2763pt}{-2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{-2.2763pt}\pgfsys@lineto{2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope \pgfsys@invoke{ }\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{% }\pgfsys@endscope\hss}}\endpgfpicture}},\hbox to4.95pt{\vbox to4.95pt{% \pgfpicture\makeatletter\hbox{\>\lower-2.4763pt\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{\the\pgflinewidth}\pgfsys@invoke{ }% \nullfont\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}} {}{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ % }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{2.2763pt}\pgfsys@lineto{-2.2763pt}{-2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{-2.2763pt}\pgfsys@lineto{-2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope {{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{2.2763pt}\pgfsys@lineto{-2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope \pgfsys@invoke{ }\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{% }\pgfsys@endscope\hss}}\endpgfpicture}},\hbox to4.95pt{\vbox to4.95pt{% \pgfpicture\makeatletter\hbox{\>\lower-2.4763pt\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{\the\pgflinewidth}\pgfsys@invoke{ }% \nullfont\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}} {}{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ % }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{2.2763pt}\pgfsys@lineto{-2.2763pt}{-2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{-2.2763pt}\pgfsys@lineto{-2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope \pgfsys@invoke{ }\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{% }\pgfsys@endscope\hss}}\endpgfpicture}}\}$ , we say that a drawing is $\mathcal{S}$ -restricted $1$ -planar if it is $1$ -planar and the type of each crossing belongs to $\mathcal{S}$ , and a graph is $\mathcal{S}$ -restricted $1$ -planar if it admits a $\mathcal{S}$ -restricted $1$ -planar drawing.

We already know that limiting the crossing types can have consequences. For instance, Biedl and Murali [4] described an algorithm to compute the vertex connectivity of a graph that is given with a $1$ -planar drawing without crossings. This was extended by Biedl, Bose and Murali [3] to allow some crossings in a controlled manner. Bose et al. [7] have shown that graphs that have a $1$ -planar -crossing-free drawing have bounded cop-number. However, it was not clear how difficult is to decide if a given graph has such a $1$ -planar drawing without crossings, and this is posed explicitly as an open problem in [4].

On the other end of the spectrum when it comes to crossing types, Brandenburg [8] has shown that the class of $1$ -planar graphs that admit $1$ -planar drawings where all crossings are crossings is equivalent to the class of $4$ -map graphs with holes, and thus $\{\hbox to4.95pt{\vbox to4.95pt{\pgfpicture\makeatletter\hbox{\>\lower-2.4763% pt\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{\the% \pgflinewidth}\pgfsys@invoke{ }\nullfont\hbox to0.0pt{\pgfsys@beginscope% \pgfsys@invoke{ }{{}} {}{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ % }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{2.2763pt}\pgfsys@lineto{-2.2763pt}{-2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{-2.2763pt}\pgfsys@lineto{-2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{-2.2763pt}{-2.2763pt}\pgfsys@lineto{2.2763pt}{-2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{-2.2763pt}\pgfsys@lineto{2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{2.2763pt}\pgfsys@lineto{-2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{-2.2763pt}{2.2763pt}\pgfsys@lineto{-2.2763pt}{-2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope \pgfsys@invoke{ }\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{% }\pgfsys@endscope\hss}}\endpgfpicture}}\}$ -restricted $1$ -planar graphs are recognizable in polynomial time. Münch and Rutter [26] show that, for each subset $\mathcal{S}$ of crossing types, recognizing $\mathcal{S}$ -restricted $1$ -planar is $\mathsf{FPT}$ with respect to the number of crossings.

Another important thread in our work is that of straight-line drawings, which we refer to as geometric drawings. It is well-known that planar graphs admit a geometric planar drawing [15, 28]. However, we know that whether in the drawing we use arbitrary curves for the edges or we use straight-line segments does affect the crossings [5]. Similar phenomena occur for $1$ -planar graphs: not all graphs that have a $1$ -planar drawing have a geometric $1$ -planar drawing. Thomassen [27] provided a criterion to know when a $1$ -planar drawing can be continuously deformed into an equivalent $1$ -planar drawing with straight-line edges. The characterization is based on forbidden configurations in the drawing; we will explain this in detail below. How to transform efficiently a $1$ -planar drawing into a geometric one has been considered by Hong et al. [20].

Our contribution.

We systematically investigate the complexity of recognizing $\mathcal{S}$ -restricted $1$ -planar graphs for every fixed, nonempty subset $\mathcal{S}$ of crossing types. Fortunately, the characterization is neat, as it does not need to go over the $63$ possible cases, and shows an interesting dichotomy when considering graphs parameterized by the treewidth:

$\blacksquare$

If $\mathcal{S}\subseteq\{\hbox to4.95pt{\vbox to4.95pt{\pgfpicture\makeatletter% \hbox{\>\lower-2.4763pt\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{\the\pgflinewidth}\pgfsys@invoke{ }\nullfont\hbox to0.0pt% {\pgfsys@beginscope\pgfsys@invoke{ }{{}} {}{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ % }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{2.2763pt}\pgfsys@lineto{-2.2763pt}{-2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{-2.2763pt}\pgfsys@lineto{-2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{-2.2763pt}{-2.2763pt}\pgfsys@lineto{2.2763pt}{-2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{-2.2763pt}\pgfsys@lineto{2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{2.2763pt}\pgfsys@lineto{-2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{-2.2763pt}{2.2763pt}\pgfsys@lineto{-2.2763pt}{-2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope \pgfsys@invoke{ }\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{% }\pgfsys@endscope\hss}}\endpgfpicture}},\hbox to4.95pt{\vbox to4.95pt{% \pgfpicture\makeatletter\hbox{\>\lower-2.4763pt\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{\the\pgflinewidth}\pgfsys@invoke{ }% \nullfont\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}} {}{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ % }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{2.2763pt}\pgfsys@lineto{-2.2763pt}{-2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{-2.2763pt}\pgfsys@lineto{-2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope {{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{-2.2763pt}\pgfsys@lineto{2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{2.2763pt}\pgfsys@lineto{-2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{-2.2763pt}{2.2763pt}\pgfsys@lineto{-2.2763pt}{-2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope \pgfsys@invoke{ }\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{% }\pgfsys@endscope\hss}}\endpgfpicture}},\hbox to4.95pt{\vbox to4.95pt{% \pgfpicture\makeatletter\hbox{\>\lower-2.4763pt\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{\the\pgflinewidth}\pgfsys@invoke{ }% \nullfont\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}} {}{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ % }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{2.2763pt}\pgfsys@lineto{-2.2763pt}{-2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{-2.2763pt}\pgfsys@lineto{-2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope {{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{-2.2763pt}\pgfsys@lineto{2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope {{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{-2.2763pt}{2.2763pt}\pgfsys@lineto{-2.2763pt}{-2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope \pgfsys@invoke{ }\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{% }\pgfsys@endscope\hss}}\endpgfpicture}}\}$ , it is $\mathsf{FPT}$ parameterized by the treewidth to recognize $\mathcal{S}$ -restricted $1$ -planar graphs.
$\blacksquare$

If $\mathcal{S}\cap\{\hbox to4.95pt{\vbox to4.95pt{\pgfpicture\makeatletter\hbox{% \>\lower-2.4763pt\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{\the% \pgflinewidth}\pgfsys@invoke{ }\nullfont\hbox to0.0pt{\pgfsys@beginscope% \pgfsys@invoke{ }{{}} {}{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ % }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{2.2763pt}\pgfsys@lineto{-2.2763pt}{-2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{-2.2763pt}\pgfsys@lineto{-2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{-2.2763pt}{-2.2763pt}\pgfsys@lineto{2.2763pt}{-2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{-2.2763pt}\pgfsys@lineto{2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope \pgfsys@invoke{ }\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{% }\pgfsys@endscope\hss}}\endpgfpicture}},\hbox to4.95pt{\vbox to4.95pt{% \pgfpicture\makeatletter\hbox{\>\lower-2.4763pt\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{\the\pgflinewidth}\pgfsys@invoke{ }% \nullfont\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}} {}{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ % }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{2.2763pt}\pgfsys@lineto{-2.2763pt}{-2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{-2.2763pt}\pgfsys@lineto{-2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope {{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{2.2763pt}\pgfsys@lineto{-2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope \pgfsys@invoke{ }\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{% }\pgfsys@endscope\hss}}\endpgfpicture}},\hbox to4.95pt{\vbox to4.95pt{% \pgfpicture\makeatletter\hbox{\>\lower-2.4763pt\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{\the\pgflinewidth}\pgfsys@invoke{ }% \nullfont\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}} {}{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ % }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{2.2763pt}\pgfsys@lineto{-2.2763pt}{-2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{-2.2763pt}\pgfsys@lineto{-2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope \pgfsys@invoke{ }\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{% }\pgfsys@endscope\hss}}\endpgfpicture}}\}\neq\emptyset$ , then it is $\mathsf{NP}$ -hard to recognize $1$ -planar graphs that are $\mathcal{S}$ -restricted $1$ -planar, even for graphs that have the treewidth bounded by constant.

Thereby we do not only resolve the open question from [4] (negatively), but we also obtain a very detailed perspective on how hard is recognizing $1$ -planar graphs with constant treewidth that admit $1$ -planar drawings with certain crossing types.

We also show that our dichotomy extends to the geometric setting, i.e. when all edges are required to be drawn as straight-line segments. Surprisingly, the same characterization works. However, extending the result to the geometric setting requires substantial effort.

Techniques.

We use the fact that we target treewidth parameterizations to be able to invoke Courcelle’s theorem [10]. However, expressing 1-planarity is something that is not possible efficiently in MSO (the logic required to formulate a problem in so that Courcelle’s theorem implies a fixed-parameter algorithm), unless ${\mathsf{FPT}}={\mathsf{W}}[1]$ . This is where restricting crossing types becomes essential. We are able to show that restricting to crossing types that force $4$ -cycles to be present on the endpoints of the crossing edges allows for encoding $1$ -planarity in MSO in a constant-length formula. The key insight to do so is to realize an elegant way in which we can identify pairs of crossing edges without explicitly coding them into an MSO-formula.

To adapt this to the geometric setting, we use the fact that small topological obstructions to geometric 1-planarity are known. As MSO cannot speak about topology, it is useful that we can first reduce to instances whose prospective planarizations have unique embeddings.

Our $\mathsf{NP}$ -hardness results are all based on a single reduction from 3-Partition which are modularly adaptable for each crossing type that does not contain a $4$ -cycle.

2 Preliminaries

We use standard terminology and notation from graph theory [13] and assume general familiarity with parameterized complexity theory [11, 14]. We explain here some concepts and conventions that perhaps are encountered less often.

Graph terminology.

All graphs we consider are simple and undirected. A separator $S$ induces a separation $(X_{1},\dots,X_{\ell})$ for some $\ell\in\mathbb{N}$ if $\cup_{1\leq i\leq\ell}X_{i}=V(G)$ and, for $1\leq i\neq j\leq\ell$ , we have $X_{i}\cap X_{j}=S$ and $S\subsetneq X_{i}\subset V(G)$ . Given a separator $S$ a separation is not necessarily unique.
We call $G$ internally 3-connected if $G$ can be obtained from a 3-connected graph $G^{\prime}$ by subdividing (with single vertices) a subset of edges of $G^{\prime}$ . (Here $G^{\prime}$ may have some parallel edges and at most one edge in each group of parallel edges is not subdivided.) The only 2-separators in an internally 3-connected graph are neighborhoods of degree-2 vertices.

If $G$ is a connected graph then a block-tree or BC-tree of $G$ is a tree $T$ whose vertices are cutvertices and blocks of $G$ , and adjacency in $T$ is defined as containment in $G$ .

A tree $T$ is the SPR-tree of a 2-connected graph $G$ , if every node $t$ of $T$ is labeled with S-, P-, or R-label, and it represents a graph, called the skeleton of $t$ and denoted $\mathrm{sk}(t)$ , whose edges are labeled real and virtual. S-nodes represent cycles, P-nodes represent dipoles, and R-nodes represent 3-connected graphs. Every edge $xy\in E(T)$ pairs a pair of directed virtual edges from $\mathrm{sk}(x)$ and $\mathrm{sk}(y)$ , respectively, and every virtual edge $e$ from $\mathrm{sk}(x)$ is paired with another virtual edge. We obtain $G$ from its SPR-tree representation by identifying pairs of paired virtual edges and deleting the identified pairs. The graphs represented by R-nodes are called 3-connected components of $G$ . The skeleton+ of an R-node $x$ , denoted $\mathrm{sk}^{+}(x)$ , is obtained from $\mathrm{sk}(x)$ by adding a real edge for every virtual edge that corresponds to an edge in $G$ and subdividing once every virtual edge. Note that the skeleton+ of an R-node is internally 3-connected.

While BC-trees are a classical concept in graph theory, SP(Q)R-trees were first described by Di Battista and Tamassia [2]. Both BC-trees and SPR-trees of a graph $G$ have size bounded by $O(|G|)$ and can be computed in linear time [18].

Graph drawing.

A characterization of planar graphs, which will be useful to us, is that a graph is planar, if and only if it does not contain a subgraph that is a subdivision of $K_{5}$ or $K_{3,3}$ [24]; such subgraphs are also called Kuratowski subdivisions.

The planarization $\mathcal{G}^{\times}$ of a 1-planar drawing $\mathcal{G}$ of a graph $G$ is obtained from $\mathcal{G}$ by replacing each pair of crossing edges with a new vertex positioned in a crossing which is linked to the endpoints of the crossing edges. Essentially this means we replace pairs of crossing edge segments by 4-claws.

A face of a drawing is a maximal connected subset of $\mathbb{R}^{2}$ that does not intersect the drawing (this implies that faces are always open sets, and this definition is also for drawings with crossings). For a simple closed curve in a drawing, a vertex is drawn inside that curve if it is separated from the outer face by that curve, and outside of that curve otherwise.

This allows us to give a useful equivalent characterization of geometric 1-planar drawings: Thomassen [27] showed that a drawing $\mathcal{G}$ can be transformed into a geometric 1-planar drawing by a homeomorphism of the plane if and only if it is 1-planar and neither of the following is contained in $\mathcal{G}$ (see Figure 1 for reference):

$\blacksquare$

Three edges $ss^{\prime}$ , $s b$ and $s^{\prime}b^{\prime}$ such that $s b$ and $s^{\prime}b$ cross and $b$ and $b^{\prime}$ are inside the closed curve given by the drawings of $ss^{\prime}$ , $s^{\prime}b^{\prime}$ from $s^{\prime}$ up to its crossing with $s b$ and $s b$ from its crossing with $s^{\prime}b^{\prime}$ up to $s$ ; such a situation is called a B-configuration.
$\blacksquare$

Four edges $sw_{1}$ , $sw_{2}$ , $s^{\prime}w^{\prime}_{1}$ and $s^{\prime}w^{\prime}_{2}$ such that $sw_{1}$ and $s^{\prime}w^{\prime}_{1}$ cross and $sw_{2}$ and $s^{\prime}w^{\prime}_{2}$ cross and $w_{1}$ , $w_{2}$ , $w^{\prime}_{1}$ and $w^{\prime}_{2}$ lie inside the closed curve given by the drawings of the four edges between their crossings and $s$ and $s^{\prime}$ ; such a situation is called a W-configuration.

In both configurations above we call the pair of vertices $s,s^{\prime}$ the spine.

Figure 1: B- and W-configuration.

We overload the term ‘boundary of a face’ to mean all the vertices, edges, edge segments and crossings whose drawings lie on the (pointwise set) boundary of a face. We say that two vertices are cofacial in a drawing if they lie together on the boundary of an arbitrary face of the drawing. It is known that in any 3-connected graph $G$ a cycle $C\subseteq G$ is the boundary of a face in any planar drawing of $G$ if and only if $G-V(C)$ is connected and $C$ is an induced cycle of $G$ ; see for example [25, Theorem 2.5.1].

Parameterized complexity.

Given a tree decomposition $(T,\chi)$ of a graph $G$ , the graph $(V(G),\{uv\mid\exists t\in V(T)\ \{u,v\}\subseteq\chi(t)\}$ is called a chordal completion of $G$ . By construction, $G$ is a subgraph of any chordal completion, such a chordal completion has treewidth at most $\operatorname{tw}(T,\chi)$ , and chordal completions are chordal, i.e. do not contain induced $4$ -cycles. Courcelle’s theorem [10, 14] states that any problem encodable by an MSO₂-sentence $\varphi$ over input graph $G$ can be decided in $\mathsf{FPT}$ -time parameterized by $\operatorname{tw}(G)+|\varphi|$ , where $|\varphi|$ is the length of the sentence $\varphi$ .

3 Fixed-Parameter Tractable Cases by Treewidth

The aim of this section is to show the following theorems.

Theorem 1.

It is $\mathsf{FPT}$ parameterized by treewidth to recognize $\mathcal{S}$ -restricted $1$ -planar graphs if $\mathcal{S}\subseteq\{\hbox to4.95pt{\vbox to4.95pt{\pgfpicture\makeatletter% \hbox{\>\lower-2.4763pt\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{\the\pgflinewidth}\pgfsys@invoke{ }\nullfont\hbox to0.0pt% {\pgfsys@beginscope\pgfsys@invoke{ }{{}} {}{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ % }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{2.2763pt}\pgfsys@lineto{-2.2763pt}{-2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{-2.2763pt}\pgfsys@lineto{-2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{-2.2763pt}{-2.2763pt}\pgfsys@lineto{2.2763pt}{-2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{-2.2763pt}\pgfsys@lineto{2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{2.2763pt}\pgfsys@lineto{-2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{-2.2763pt}{2.2763pt}\pgfsys@lineto{-2.2763pt}{-2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope \pgfsys@invoke{ }\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{% }\pgfsys@endscope\hss}}\endpgfpicture}},\hbox to4.95pt{\vbox to4.95pt{% \pgfpicture\makeatletter\hbox{\>\lower-2.4763pt\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{\the\pgflinewidth}\pgfsys@invoke{ }% \nullfont\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}} {}{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ % }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{2.2763pt}\pgfsys@lineto{-2.2763pt}{-2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{-2.2763pt}\pgfsys@lineto{-2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope {{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{-2.2763pt}\pgfsys@lineto{2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{2.2763pt}\pgfsys@lineto{-2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{-2.2763pt}{2.2763pt}\pgfsys@lineto{-2.2763pt}{-2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope \pgfsys@invoke{ }\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{% }\pgfsys@endscope\hss}}\endpgfpicture}},\hbox to4.95pt{\vbox to4.95pt{% \pgfpicture\makeatletter\hbox{\>\lower-2.4763pt\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{\the\pgflinewidth}\pgfsys@invoke{ }% \nullfont\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}} {}{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ % }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{2.2763pt}\pgfsys@lineto{-2.2763pt}{-2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{-2.2763pt}\pgfsys@lineto{-2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope {{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{-2.2763pt}\pgfsys@lineto{2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope {{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{-2.2763pt}{2.2763pt}\pgfsys@lineto{-2.2763pt}{-2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope \pgfsys@invoke{ }\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{% }\pgfsys@endscope\hss}}\endpgfpicture}}\}$ .

Theorem 2.

It is $\mathsf{FPT}$ parameterized by treewidth to recognize geometric $\mathcal{S}$ -restricted $1$ -planar graphs if $\mathcal{S}\subseteq\{\hbox to4.95pt{\vbox to4.95pt{\pgfpicture\makeatletter% \hbox{\>\lower-2.4763pt\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{\the\pgflinewidth}\pgfsys@invoke{ }\nullfont\hbox to0.0pt% {\pgfsys@beginscope\pgfsys@invoke{ }{{}} {}{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ % }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{2.2763pt}\pgfsys@lineto{-2.2763pt}{-2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{-2.2763pt}\pgfsys@lineto{-2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{-2.2763pt}{-2.2763pt}\pgfsys@lineto{2.2763pt}{-2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{-2.2763pt}\pgfsys@lineto{2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{2.2763pt}\pgfsys@lineto{-2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{-2.2763pt}{2.2763pt}\pgfsys@lineto{-2.2763pt}{-2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope \pgfsys@invoke{ }\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{% }\pgfsys@endscope\hss}}\endpgfpicture}},\hbox to4.95pt{\vbox to4.95pt{% \pgfpicture\makeatletter\hbox{\>\lower-2.4763pt\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{\the\pgflinewidth}\pgfsys@invoke{ }% \nullfont\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}} {}{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ % }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{2.2763pt}\pgfsys@lineto{-2.2763pt}{-2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{-2.2763pt}\pgfsys@lineto{-2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope {{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{-2.2763pt}\pgfsys@lineto{2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{2.2763pt}\pgfsys@lineto{-2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{-2.2763pt}{2.2763pt}\pgfsys@lineto{-2.2763pt}{-2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope \pgfsys@invoke{ }\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{% }\pgfsys@endscope\hss}}\endpgfpicture}},\hbox to4.95pt{\vbox to4.95pt{% \pgfpicture\makeatletter\hbox{\>\lower-2.4763pt\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{\the\pgflinewidth}\pgfsys@invoke{ }% \nullfont\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}} {}{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ % }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{2.2763pt}\pgfsys@lineto{-2.2763pt}{-2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{-2.2763pt}\pgfsys@lineto{-2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope {{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{-2.2763pt}\pgfsys@lineto{2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope {{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{-2.2763pt}{2.2763pt}\pgfsys@lineto{-2.2763pt}{-2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope \pgfsys@invoke{ }\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{% }\pgfsys@endscope\hss}}\endpgfpicture}}\}$ .

Throughout this section, fix $\mathcal{S}\subseteq\{\hbox to4.95pt{\vbox to4.95pt{\pgfpicture\makeatletter% \hbox{\>\lower-2.4763pt\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{\the\pgflinewidth}\pgfsys@invoke{ }\nullfont\hbox to0.0pt% {\pgfsys@beginscope\pgfsys@invoke{ }{{}} {}{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ % }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{2.2763pt}\pgfsys@lineto{-2.2763pt}{-2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{-2.2763pt}\pgfsys@lineto{-2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{-2.2763pt}{-2.2763pt}\pgfsys@lineto{2.2763pt}{-2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{-2.2763pt}\pgfsys@lineto{2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{2.2763pt}\pgfsys@lineto{-2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{-2.2763pt}{2.2763pt}\pgfsys@lineto{-2.2763pt}{-2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope \pgfsys@invoke{ }\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{% }\pgfsys@endscope\hss}}\endpgfpicture}},\hbox to4.95pt{\vbox to4.95pt{% \pgfpicture\makeatletter\hbox{\>\lower-2.4763pt\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{\the\pgflinewidth}\pgfsys@invoke{ }% \nullfont\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}} {}{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ % }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{2.2763pt}\pgfsys@lineto{-2.2763pt}{-2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{-2.2763pt}\pgfsys@lineto{-2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope {{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{-2.2763pt}\pgfsys@lineto{2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{2.2763pt}\pgfsys@lineto{-2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{-2.2763pt}{2.2763pt}\pgfsys@lineto{-2.2763pt}{-2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope \pgfsys@invoke{ }\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{% }\pgfsys@endscope\hss}}\endpgfpicture}},\hbox to4.95pt{\vbox to4.95pt{% \pgfpicture\makeatletter\hbox{\>\lower-2.4763pt\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{\the\pgflinewidth}\pgfsys@invoke{ }% \nullfont\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}} {}{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ % }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{2.2763pt}\pgfsys@lineto{-2.2763pt}{-2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{-2.2763pt}\pgfsys@lineto{-2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope {{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{-2.2763pt}\pgfsys@lineto{2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope {{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{-2.2763pt}{2.2763pt}\pgfsys@lineto{-2.2763pt}{-2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope \pgfsys@invoke{ }\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{% }\pgfsys@endscope\hss}}\endpgfpicture}}\}$ . Observe that in this case every pair of edges defining a crossing lie on a common $4$ -cycle.

Parameterizing by treewidth in principle allows us to employ the powerful machinery of Courcelle’s theorem which has previously been useful in the design of fixed-parameter algorithms for variants of the crossing number problem: Specifically in an MSO-formula one can quantify over a bounded number of pairs of subdivision vertices which should correspond to crossing vertices in the planarization of a desired drawing, ensuring that said planarization contains no Kuratowski subdivision (and in the geometric setting also no planarized B- or W-configuration). Explicitly quantifying over each pair of subdivision vertices which are “fused” into a crossing vertex results in such a formula’s length being bounded in the number of crossings, which is prohibitive for obtaining an FPT-algorithm via Courcelle’s theorem if the number of crossings is not bounded in the parameter. It is obvious that this difficulty also applies to recognizing (geometric) $\mathcal{S}$ -restricted $1$ -planar graphs.

On a high level, we overcome this difficulty by quantifying over an unpaired set of subdivision vertices (this can be done using a single variable) and deriving an unambiguous pairing of them using the $4$ -cycle on the endpoints of the corresponding edges that needs to exist because of the only crossing types we allow.

As a preparatory step for such an unambiguous pairing to be possible (how this is used will become clear in the proof of Lemma 9), we first argue that we can reduce to a setting in which we consider internally 3-connected graphs (at the expense of slightly generalizing the problem we consider). This will be carried out in Section 3.1.

Then deriving a pairing and formulating an appropriate MSO-encoding is carried out in Section 3.2 for Theorem 1 and Section 3.2.2 for Theorem 2.

3.1 Reducing to Internally 3-Connected Instances

Through a sequence of reductions that manipulate drawings of subgraphs, one can reduce deciding $\mathcal{S}$ -restricted $1$ -planarity to internally 3-connected graphs. We state the result here and invite the reader to the full version for details.

Theorem 3.

A graph is $\mathcal{S}$ -restricted $1$ -planar if and only if the skeleton+ of each of its 3-connected components is $\mathcal{S}$ -restricted $1$ -planar.

We can carry out the arguments with the goal of also arriving at internally 3-connected graphs in the geometric setting. Notice that because the choice of the outer face matters for geometric $\mathcal{S}$ -restricted $1$ -planar drawings, we need to consider a generalization of the problem of recognizing $\mathcal{S}$ -restricted $1$ -planar graphs that takes this into account appropriately.

A graph $G=(V,E)$ is $O$ -geometric $\mathcal{S}$ -restricted $1$ -planar for some $O\subset V$ with $|O|\leq 1$ , if there is a geometric $\mathcal{S}$ -restricted $1$ -planar drawing of $G$ where the vertex from $O$ , if it exists, is on the outer face. To ultimately arrive at internally 3-connected instances we need a sequence of lemmas. We show one of them, without proof, to showcase the nuances of the procedure. See [8, Lemma 1] for a similar statement.

Lemma 4.

Let $G=(V,E)$ be a $2$ -connected graph, $O\subset V$ with $|O|\leq 1$ , $s$ a cutvertex. Further let $(X_{1},\dots,X_{\ell})$ be a separation induced by $s$ and $G_{i}=G[X_{i}]$ for $i\in\{1,\dots,\ell\}$ , such that $s$ is not a cutvertex of $G_{i}$ for any $i\in\{1,\dots,\ell\}$ . Then $G$ is $O$ -geometric $\mathcal{S}$ -restricted $1$ -planar if and only if $O\subset G_{i}$ for some $i\in\{1,\dots,\ell\}$ and both $G_{i}$ is $O$ -geometric $\mathcal{S}$ -restricted $1$ -planar and for all $j\in\{1,\dots,\ell\}\setminus\{i\}$ , $G_{j}$ is $\{s\}$ -geometric $\mathcal{S}$ -restricted $1$ -planar.

Theorem 5.

Given an $\mathsf{FPT}$ -algorithm parameterized by treewidth that decides whether internally $3$ -connected graphs are $O$ -geometric $\mathcal{S}$ -restricted $1$ -planar, we can formulate an $\mathsf{FPT}$ -algorithm parameterized by treewidth to decide whether general graphs are geometric $\mathcal{S}$ -restricted $1$ -planar.

Proof sketch.

It is obvious that deciding geometric $\mathcal{S}$ -restricted 1-planarity is equivalent to deciding $\emptyset$ -geometric $\mathcal{S}$ -restricted 1-planarity.

Using Lemma 4, we can formulate a leaves-to-root dynamic program along the BC-tree of our input graph $G$ which makes calls to a subroutine that decides whether 2-connected graphs are $O$ -geometric $\mathcal{S}$ -restricted $1$ -planar for some given $O$ of cardinality at most 1. Such a subroutine can in turn be formulated as a leaves-to-root dynamic program along the SPR-tree of a 2-connected graph. If no R-node is present in the considered subtree, then the corresponding graph is planar and any specified vertex can be placed on the outer face. As soon as an R-node is present, we can dynamically reduce to internally $3$ -connected instances, which are essentially the skeleton+ of the $R$ -node, and solve them using the $\mathsf{FPT}$ -algorithm for that type of instances. Overall, during the dynamic program, there are a linear number of calls made to the solver for internally $3$ -connected graphs and only a polynomial-time overhead apart from that. $\hfill\blacktriangleleft$

3.2 An MSO-Encoding

We first focus on the non-geometric setting and describe how to adapt our formula towards solving the geometric setting in Section 3.2.2. So, until then fix $G$ to be an instance of $\mathcal{S}$ -restricted $1$ -planar such that $G$ is internally 3-connected and $\operatorname{tw}(G)\leq k$ .

Our strategy to show fixed-parameter tractability is by giving a constant-length MSO-encoding of a graph $G$ being $\mathcal{S}$ -restricted $1$ -planar (or a graph $G$ with a singleton-set $O$ of outer face required vertices being geometric $\mathcal{S}$ -restricted $1$ -planar) on an auxiliary graph $\tilde{G}$ whose treewidth is not significantly larger than that of $G$ .

Our MSO-encoding will express that there exist some pairs of edges which occur in some subgraph of $G$ isomorphic to a graph in $\mathcal{S}$ such that if we assume these pairs are all pairs of crossing edges, the resulting planarization contains no Kuratowski subdivisions, i.e. is planar, or in the geometric setting additionally contains no B- or W-configuration.

Expressing the non-existence of a constant-size obstruction such as a Kuratowski subdivision in a planarization after explicitly identifying pairs of crossing edges is not difficult and has previously been done e.g. in the fixed parameter algorithm for (non-local) Crossing Number [17]. To be explicit, before applying Courcelle’s theorem, one can subdivide each edge with a vertex corresponding to a possible crossing vertex in the planarization in case that edge is crossed. Then, given explicit access to pairs of crossing edges, the MSO-formula precludes the existence of the constant-size obstruction in the planarization by explicitly forbidding vertices and edges that can form that obstruction when the original edge relation of the graph is replaced by two vertices being endpoints of an original edge or an edge subdivision vertex for an edge $e$ and a neighbor of the subdivision vertex for the edge $e^{\prime}$ for which $e$ and $e^{\prime}$ are a pair of crossing edges.

However, we do not have explicit access to all pairs of crossing edges. In a setting where the total number of crossings is a parameter, this difficulty is easily overcome by quantifying with variables over possible crossing edge pairs. However, in this way the length of the formula depends on the number of such pairs and hence this approach is infeasible when there can be one crossing per edge. We will have to implicitly encode the pairs of crossing edges instead. For this, the restricted types of allowed crossings are critical.

3.2.1 Identifying planarized crossings

To build $\tilde{G}$ , we augment $G$ in two ways: Similarly as in [17], for every edge of $G$ we insert a $P_{3}$ between its endpoints and label the new middle vertex with $\mathtt{cr}$ . In MSO, selecting a set of $\mathtt{cr}$ -vertices encodes that the corresponding edges are crossing edges.

However, merely selecting a set of crossing edges is insufficient to describe and then check planarity of a prospective planarization. We also need to identify which pairs of crossing edges cross each other. To pair up the crossing edges, ideally we would want MSO to be able to select for a crossing edge the two end vertices of the edge it crosses, e.g., by $\tilde{G}$ having a vertex between the four end vertices of every pair of edges that could possibly cross. But this is not possible to do in general without $\operatorname{tw}(\tilde{G})$ becoming unbounded in $\operatorname{tw}(G)$ . Instead, we do the next best thing: We augment $\tilde{G}$ in such a way that MSO can select for every crossing edge one of the end vertices of the edge it crosses. Because in every crossing type $s\in\{\hbox to4.95pt{\vbox to4.95pt{\pgfpicture\makeatletter\hbox{\>\lower-2.4% 763pt\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{\the% \pgflinewidth}\pgfsys@invoke{ }\nullfont\hbox to0.0pt{\pgfsys@beginscope% \pgfsys@invoke{ }{{}} {}{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ % }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{2.2763pt}\pgfsys@lineto{-2.2763pt}{-2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{-2.2763pt}\pgfsys@lineto{-2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{-2.2763pt}{-2.2763pt}\pgfsys@lineto{2.2763pt}{-2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{-2.2763pt}\pgfsys@lineto{2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{2.2763pt}\pgfsys@lineto{-2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{-2.2763pt}{2.2763pt}\pgfsys@lineto{-2.2763pt}{-2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope \pgfsys@invoke{ }\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{% }\pgfsys@endscope\hss}}\endpgfpicture}},\hbox to4.95pt{\vbox to4.95pt{% \pgfpicture\makeatletter\hbox{\>\lower-2.4763pt\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{\the\pgflinewidth}\pgfsys@invoke{ }% \nullfont\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}} {}{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ % }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{2.2763pt}\pgfsys@lineto{-2.2763pt}{-2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{-2.2763pt}\pgfsys@lineto{-2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope {{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{-2.2763pt}\pgfsys@lineto{2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{2.2763pt}\pgfsys@lineto{-2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{-2.2763pt}{2.2763pt}\pgfsys@lineto{-2.2763pt}{-2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope \pgfsys@invoke{ }\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{% }\pgfsys@endscope\hss}}\endpgfpicture}},\hbox to4.95pt{\vbox to4.95pt{% \pgfpicture\makeatletter\hbox{\>\lower-2.4763pt\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{\the\pgflinewidth}\pgfsys@invoke{ }% \nullfont\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}} {}{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ % }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{2.2763pt}\pgfsys@lineto{-2.2763pt}{-2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{-2.2763pt}\pgfsys@lineto{-2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope {{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{-2.2763pt}\pgfsys@lineto{2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope {{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{-2.2763pt}{2.2763pt}\pgfsys@lineto{-2.2763pt}{-2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope \pgfsys@invoke{ }\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{% }\pgfsys@endscope\hss}}\endpgfpicture}}\}$ there is a $4$ -cycle that includes both crossing edges of $s$ , this essentially asks MSO to select for each crossing, two paths of length two that together form a $4$ -cycle.

To do so, we compute a tree decomposition $(T,\chi)$ of $G$ of width $\mathcal{O}(\operatorname{tw}(G))$ [6] and use this to construct a chordal completion $\hat{G}$ of treewidth $\mathcal{O}(\operatorname{tw}(G))$ . For every $4$ -tuple of edges $(e,f,e^{\prime},f^{\prime})\in E(G)^{4}$ forming a $4$ -cycle in $G$ (in that order), the chordality of $\hat{G}$ implies that there is at least one chord edge for $(e,f,e^{\prime},f^{\prime})$ : an edge $g\in E(\hat{G})\setminus\{e,f,e^{\prime},f^{\prime}\}$ connecting two vertices of $e\cup f\cup e^{\prime}\cup f^{\prime}$ . For each $4$ -cycle $(e,f,e^{\prime},f^{\prime})$ whose vertices induce a graph underlying a crossing type in $\mathcal{S}$ where $e$ and $e^{\prime}$ cross and each chord $g$ for $(e,f,e^{\prime},f^{\prime})$ , we iteratively add the following graph elements to $\tilde{G}$ : A $P_{3}$ between the endpoints of $g$ with a new middle vertex labeled $\mathtt{ctp}$ and an edge between the $\mathtt{ctp}$ vertex and the $\mathtt{cr}$ -vertex that was inserted for $e$ . We call $(e,g)$ a chord-tied pair, if $e$ is not incident to a degree $2$ vertex in $G$ . We call $e$ the crossing edge and $g$ the chord edge of this chord-tied pair. Each chord-tied pair is uniquely identified by a $\mathtt{ctp}$ -vertex.

At this point, for a given chord-tied pair, there might be multiple other chord-tied pairs with the same chord edge. See, e.g., the right of Figure 2, where there are four chord-tied pairs $(e,g)$ , $(e^{\prime},g)$ , $(\overline{e},g)$ , and $(\overline{e}^{\prime},g)$ with the same chord edge $g$ . This is why we add two flag pendants labeled $\mathtt{0}$ and $\mathtt{1}$ to each $\mathtt{ctp}$ vertex in $\tilde{G}$ to encode a boolean flag for every chord-tied pair; see the left side of Figure 2 for an illustration. A pair of edges $\{e,e^{\prime}\}$ is called a crossing pair if $e$ and $e^{\prime}$ are the crossing edges of two different chord-tied pairs with the same chord edge and the same flag. For this definition to be able to uniquely identify which edges cross, at most four chord-tied pairs can share a chord edge, but as we show in Lemma 9 this suffices for internally 3-connected $\mathcal{S}$ -restricted $1$ -planar graphs.

This completes our construction of $\tilde{G}$ . First we bound its treewidth.

Lemma 6.

$\operatorname{tw}(\tilde{G})\in\mathcal{O}(\operatorname{tw}(G)^{2})$ .

Figure 2: (left) chord-tied pair

(e,g)

with central vertex

u

and flag pendants, (right) chord edge with two crossings.

The next definition allows us to associate chord tied pairs and flags with pairings of crossings.

Definition 7 (chord description).

A set $\mathrm{CD}$ of chord-tied pairs with flags (i.e., a set of tuples $(e,g,b)$ , where $(e,g)$ is a chord-tied pair and $b\in\{0,1\}$ ) is a chord description of $G$ , if it satisfies the following conditions:

1.

for every chord-tied pair in $\mathrm{CD}$ there is exactly one other chord-tied pair in $\mathrm{CD}$ with the same chord edge and flag; if $(e,g,b)$ and $(e^{\prime},g,b)$ belong to $\mathrm{CD}$ , we say that $\{e,e^{\prime}\}$ form a crossing pair of $\mathrm{CD}$ ;
2.

every edge is the crossing edge of at most one chord-tied pair in $\mathrm{CD}$ ;
3.

the graph $G_{\mathrm{CD}}$ , where, starting with $G$ , every crossing pair $\{e,e^{\prime}\}$ of $\mathrm{CD}$ is replaced by a 4-claw on $V(\{e,e^{\prime}\})$ , is planar; and
4.

every crossing pair $\{e,e^{\prime}\}$ of $\mathrm{CD}$ can cross $\mathcal{S}$ -restricted $1$ -planarly, i.e., the vertices in $e\cup e^{\prime}$ induce a crossing type from $\mathcal{S}$ where $e$ and $e^{\prime}$ cross.

We can derive a drawing from a chord description as follows.

Lemma 8.

Let $\mathrm{CD}$ be a chord description of $G$ . Then there is an $\mathcal{S}$ -restricted $1$ -planar drawing of $G$ where only crossings pairs of $\mathrm{CD}$ cross.

Proof.

We start with a planar drawing $\mathcal{G}_{\mathrm{CD}}$ of $G_{\mathrm{CD}}$ , which exists by Item 3. Then, we un-replace in $\mathcal{G}_{\mathrm{CD}}$ every 4-claw corresponding to a crossing pair of $\mathrm{CD}$ by its original edges. This essentially corresponds to undoing a planarization and yields a drawing $\mathcal{G}$ of $G$ where only crossing pairs of $\mathrm{CD}$ cross. (Notice that the un-replacement of 4-claws corresponding to a crossing pair of a -crossing does not necessarily yield a crossing in $\mathcal{G}$ because the endpoints of the edges of the crossing pair might not alternate in the rotation around the center of the 4-claw, but for - and -crossings it always does.) By Item 2 and the definition of crossing pairs, each edge is crossed at most once in $\mathcal{G}$ . By Item 4, each crossing in $\mathcal{G}$ is an $\mathcal{S}$ -restricted $1$ -planar one. Therefore, $\mathcal{G}$ is an $\mathcal{S}$ -restricted $1$ -planar drawing of $G$ where only crossing pairs of $\mathrm{CD}$ cross. $\hfill\blacktriangleleft$

Conversely, we can derive a chord description from a hypothetical $\mathcal{S}$ -restricted $1$ -planar drawing of $G$ . Here the internal 3-connectivity of $G$ is important; see Figure 3.

Figure 3: In a chordal graph arising from adding an even number of distinct triangles tips to a shared edge, the shared edge is the only chord and selecting the blue edges, i.e. the edges between the tip and one shared endpoint for one half of the triangles and the edges between the tip and the other shared endpoint for the other half allows for a quadratic number of possible crossing pairs, namely any pairing of independent blue edges. This ambiguity arises because this graph is only 2- and not 3-connected.

Lemma 9.

Let $G$ be an internally $3$ -connected graph that has an $\mathcal{S}$ -restricted $1$ -planar drawing. Then there exists a chord description $\mathrm{CD}$ such that for every chord-tied pair in $\mathrm{CD}$ there is an edge in $\hat{G}$ between its chord vertices.

Proof.

We do this proof by constructing $\mathrm{CD}$ from some $\mathcal{S}$ -restricted $1$ -planar drawing $\mathcal{G}$ of $G$ . One can show that, if $G$ is an internally $3$ -connected graph that has an $\mathcal{S}$ -restricted $1$ -planar drawing, then there is an $\mathcal{S}$ -restricted $1$ -planar drawing of $G$ where no edge participating in a crossing has an endpoint of degree $2$ . We consider such a drawing $\mathcal{G}$ . For every crossing in $\mathcal{G}$ we can construct two (different) chord-tied pairs with the same chord edge and the same flag, because the pair of edges is on a $4$ -cycle which has to have a chord in $\hat{G}$ . By Item 1 of being a chord description, the construction directly guarantees that each chord-tied pair has at least one partner. If we can show that every chord-tied pair has exactly one partner, then $\mathrm{CD}$ trivially also satisfies Items 3, 4, and 2. In $\mathcal{G}$ two crossings whose corresponding chord-tied pairs have the same chord vertices enclose a region that only consists of edges that already cross and this face is only incident to the chord vertices. Having a third such crossing would force one of the three crossings to be completely inside such a region. By $G$ being internally 3-connected this can only happen if the crossing edges have degree- $2$ endpoints, which is not the case in $\mathcal{G}$ . Therefore, we can choose the flags such that there are at most two chord-tied pairs in $\mathrm{CD}$ that share both the flag and the chord edge. $\hfill\blacktriangleleft$

Building an MSO₂-formula.

The intuition behind the forthcoming formula is to select a subset $D$ of $\mathtt{ctp}$ -vertices, which is equivalent to selecting a subset of chord-tied pairs, and select for each $\mathtt{ctp}$ -vertex a unique flag $\mathtt{0}$ or $\mathtt{1}$ such that the resulting chord-tied pairs with flags form a chord description. Thus, the general structure of the MSO₂-formula $\varphi$ which we want to apply Courcelle’s theorem to will be as follows:

$\displaystyle\varphi:=\exists D\exists M\$	$\displaystyle\forall d\in D\ \mathtt{ctp}(d)\land\forall m\in M\ \mathtt{0}(m)% \lor\mathtt{1}(m)$	(1)
	$\displaystyle\land\forall d\in D\ \big(\exists m\in M\ \textsc{adj}(d,m)\land% \forall m^{\prime}\in M\ (\textsc{adj}(d,m^{\prime})\Rightarrow m=m^{\prime})\big)$	(2)
	$\displaystyle\land\forall m\in M\ \exists d\in D\ \textsc{adj}(d,m)$	(3)
	$\displaystyle\land\textsc{ChordDescription}(D,M),$	(4)

where ChordDescription $(D,M)$ encodes that $D$ with each chord tied pair corresponding to $d\in D$ receiving the flag coinciding with the label of the unique (by (2)) neighbor of $d$ in $M$ is a chord description of $G$ .

The encoding of ChordDescription $(D,M)$ is done formulating each of the conditions from Definition 7. The description is technical and tedious; we refer the reader to the full version.

Lemma 10.

Definition 7 holding for a set $D$ of chord-tied pairs if flagged according to a unique matching to a set $M$ of flag pendants can be encoded as a constant-length MSO₂-formula with free variables $D$ and $M$ .

Combining Lemmata 8, 9, and 10 we easily obtain the following.

Corollary 11.

Let $G$ be an internally $3$ -connected graph. Then $\tilde{G}\models\varphi$ if and only if $G$ is a yes-instance for $\mathcal{S}$ -restricted $1$ -planar.

Since the formula $\varphi$ in Corollary 11 has constant length and $\operatorname{tw}(\tilde{G})\in\mathcal{O}(\operatorname{tw}(G)^{2})$ (because of Lemma 6), we can apply Courcelle’s theorem to conclude that for internally $3$ -connected graphs there is an $\mathsf{FPT}$ -algorithm parameterized by treewidth to recognize whether they are $\mathcal{S}$ -restricted $1$ -planar graphs. Theorem 1 now follows from Theorem 3.

3.2.2 Encoding Straightline Planarity

Now we turn to the geometric setting, i.e. recognizing $\mathcal{S}$ -restricted $1$ -planar graphs. One difference is that we need to additionally express the non-existence of planarized B- and W-configurations in the graph corresponding to the planarization of a $\mathcal{S}$ -restricted $1$ -planar drawing. Further, by Lemma 4 and other similar-looking statements to reduce the problem to the case of internally $3$ -connected graphs, we need to additionally allow requiring the containment of some distinguished vertex on the outer face.

For expressing outer-face requirement, we consider the distinguished vertex colored with outer in the graph when we apply Courcelle’s theorem if there is any.

For expressing the non-existence of planarized B- and W-configurations, notice that quantifying over all abstract graphs underlying them is trivially possible in MSO.

To forbid the actual drawings that constitute B- and W-configurations, it will be convenient to consider a certain kind of well-behaved geometric $\mathcal{S}$ -restricted $1$ -planar drawings.

Definition 12.

A geometric $\mathcal{S}$ -restricted $1$ -planar drawing $\mathcal{G}$ is crossing confined if for each crossing, say between edges $e$ and $e^{\prime}$ , no other edge between any pair of vertices among the endpoints of $e$ and $e^{\prime}$ is involved in a crossing.

Observation 13.

If there is a geometric $\mathcal{S}$ -restricted $1$ -planar drawing of $G$ then there is also a crossing confined one. Every outer face vertex in the old drawing is also an outer face vertex in the new drawing.

Proof.

Assume $v_{1}v_{2},u_{1}u_{2}$ is an arbitrary pair of mutually crossing edges in $\mathcal{G}$ . We want to find a geometric $\mathcal{S}$ -restricted $1$ -planar drawing in which none of the (potentially existing) edges $v_{1}u_{1},u_{1}v_{2},v_{2}u_{2},u_{2}v_{1}$ are crossed. Without loss of generality we may focus on vertices $u_{1}$ and $v_{1}$ and assume that $u_{1}v_{1}\in E(G)$ . Let $c$ be the vertex in the planarization $\mathcal{G}^{\times}$ corresponding to the crossing of edges $v_{1}v_{2}$ and $u_{1}u_{2}$ . Note that vertices $v_{1}$ and $u_{1}$ are consecutive around $c$ in the planarization $\mathcal{G}^{\times}$ and are therefore cofacial in $\mathcal{G}$ . The edge $u_{1}v_{1}$ , if crossed, can be redrawn without a crossing. Doing this at an epsilon distance from some pairwise crossing edges incident to $u_{1}$ and $v_{1}$ , respectively (which is not necessarily the pair $v_{1}v_{2},u_{1}u_{2}$ ), does not introduce new B- or W-configurations, so the resulting drawing can be geometrically realized. $\hfill\blacktriangleleft$

If we assume crossing confinedness of a targeted solution, which we can do without loss of generality, then the only way in which the abstract graphs underlying planarized B- and W-configurations can occur in a geometric 1-planar drawing is if a specific face is not the outer face. We provide a lemma for each configuration.

Lemma 14.

A crossing confined 1-planar drawing $\mathcal{H}$ of an internally 3-connected graph $H$ contains a B-configuration on edges $ss^{\prime}$ , $s b$ and $s^{\prime}b^{\prime}$ in which $s b$ and $s^{\prime}b^{\prime}$ cross if and only if the crossing between $s b$ and $s^{\prime}b^{\prime}$ together with $s$ and $s^{\prime}$ are precisely the set of vertices on the boundary of the outer face of $\mathcal{H}^{\times}-\{v\in V(G)\setminus\{b,b^{\prime}\}\mid N(v)=\{s,s^{% \prime}\}\}$ .

Proof.

$\Rightarrow$ Because $\mathcal{H}$ is 1-planar there are no edges crossing $s b$ other than $s^{\prime}b^{\prime}$ and vice versa. Because $\mathcal{H}$ is crossing confined, $ss^{\prime}$ is not involved in any crossing. This means that if there are vertices drawn outside of the closed curve given by $ss^{\prime}$ and $s^{\prime}b^{\prime}$ from $s^{\prime}$ to its crossing and $s b$ from its crossing to $s$ , then they must be connected to $b$ only by paths through $s$ or $s^{\prime}$ . However, this contradicts the fact that $H$ is internally 3-connected unless the vertices are of degree 2 and only neighboring $s$ and $s^{\prime}$ , implying that there are no other vertices outside of that curve and it has to be the boundary of the outer face.

$\Leftarrow$ By contraposition, if $s$ , $s^{\prime}$ , and the crossing between $s b$ and $s^{\prime}b^{\prime}$ are the only vertices on the outer face of $\mathcal{H}^{\times}$ after deleting all degree-2 vertices with neighbors exactly $s,s^{\prime}$ then $b$ and $b^{\prime}$ are drawn inside the curve given by $ss^{\prime}$ and $s^{\prime}b^{\prime}$ from $s^{\prime}$ to its crossing and $s b$ from its crossing to $s$ . This implies a B-configuration in $\mathcal{H}$ . $\hfill\blacktriangleleft$

Without even using crossing confinedness (but just the fact that in 1-planar drawings each edge is involved in at most one crossing), one can show a similar statement for W-configurations.

Lemma 15.

A crossing confined 1-planar drawing $\mathcal{H}$ of an internally 3-connected graph $H$ contains a W-configuration with spine $s,s^{\prime}$ on edges $sw_{1}$ , $sw_{2}$ , $s^{\prime}w^{\prime}_{1}$ and $s^{\prime}w^{\prime}_{2}$ in which $sw_{1}$ and $sw_{2}$ and also $s^{\prime}w^{\prime}_{1}$ and $s^{\prime}w^{\prime}_{2}$ cross each other if and only if their crossings together with $s$ and $s^{\prime}$ are precisely the set of vertices on the boundary of the outer face of $\mathcal{H}^{\times}-\{v\in V(G)\setminus\{w_{1},w_{2},w^{\prime}_{1},w^{% \prime}_{2}\}\mid N(v)=\{s,s^{\prime}\}\}$ .

Overall, this means we can expand $\varphi$ from the previous subsection as follows for the geometric setting:

	$\displaystyle\hskip-13.00005pt\varphi_{\text{geom}}:$	$\displaystyle=\varphi\land\textsc{cr-confined}(D,F)\land$
		$\displaystyle\begin{aligned} \big(&\exists C\ \textsc{facecycle}(C)\\ &\land(\forall v\ \texttt{outer}(v)\Rightarrow(v\in C\lor(\exists n_{1},n_{2}% \in C\forall w\ \textsc{adj}(v,w)\Rightarrow w=n_{1}\lor w=n_{2}))\\ &\land(\forall b_{1},b_{2},b_{3},b_{4},b_{5},c\ \textsc{B-config}(b_{1},\dotsc% ,b_{5},c)\Rightarrow C\neq\{b_{1},b_{2},c\})\\ &\land(\forall b_{1},b_{2},b_{3},b_{4},b_{5},b_{6},c_{1},c_{2}\ \textsc{W-% config}(b_{1},\dotsc,b_{6},c_{1},c_{2})\Rightarrow C\neq\{b_{1},b_{2},c_{1},c_% {2}\})\big),\end{aligned}$

where if from the flagged chord-description quantified over in $\varphi$ we get $\mathrm{CD}$ ,

$\blacksquare$

cr-confined $(D,F)$ expresses that for each crossing pair $\{e,e^{\prime}\}$ of the chord description $\mathrm{CD}$ encoded by $(D,F)$ , there is no crossing pair of $\mathrm{CD}$ containing another edge between any pair of endpoints of $e$ and $e^{\prime}$ .
$\blacksquare$

facecycle $(C)$ expresses that $G_{\mathrm{CD}}[C]$ is an induced non-separating cycle after the contraction of degree-2 vertices.
$\blacksquare$

B-config $(b_{1},\dotsc,b_{4},c)$ expresses the existence of the underlying graph of a planarized and uncrossed-edge-subdivided B-configuration with crossing vertex $c$ and uncrossed subdivided edge $b_{1}b_{2}$ in $G_{\mathrm{CD}}$ .
$\blacksquare$

W-config $(b_{1},\dotsc,b_{6},c_{1},c_{2})$ expresses the existence of the underlying graph of a planarized W-configuration with crossing vertices $c_{1}$ and $c_{2}$ and shared endpoints of original edges $b_{1}$ and $b_{2}$ in $G_{\mathrm{CD}}$ .

It is easy to see that the above can be expressed as a constant-length MSO-formula (where the main difficulty lies in encoding the set of crossing pairs of the chord description encoded by $(D,F)$ and $G_{\mathrm{CD}}$ which we argued how to do in the previous subsection.

Lemma 16.

Let $G$ be an internally $3$ -connected graph. Then $\tilde{G}\models\varphi_{\text{geom}}$ if and only if $G$ is geometric $\mathcal{S}$ -restricted $1$ -planar and there is a geometric $\mathcal{S}$ -restricted $1$ -planar drawing of $G$ in which all outer-colored vertices are on the outer face.

Since the formula $\varphi$ in Lemma 16 has constant length and $\operatorname{tw}(\tilde{G})\in\mathcal{O}(\operatorname{tw}(G)^{2})$ (because of Lemma 6), we can apply Courcelle’s theorem to conclude that there is an $\mathsf{FPT}$ -algorithm parameterized by treewidth that decides whether internally $3$ -connected graphs are $O$ -geometric $\mathcal{S}$ -restricted $1$ -planar. Theorem 2 now follows from Theorem 5.

4 Hard Cases for Constant Pathwidth

In this section we show that for the remaining subsets of crossing types, the recognition problem becomes $\mathsf{NP}$ -complete in the geometric and non-geometric case, even if the graph has constant pathwidth.

Theorem 17.

For $\mathcal{S}\cap\{\hbox to4.95pt{\vbox to4.95pt{\pgfpicture\makeatletter\hbox{% \>\lower-2.4763pt\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{\the% \pgflinewidth}\pgfsys@invoke{ }\nullfont\hbox to0.0pt{\pgfsys@beginscope% \pgfsys@invoke{ }{{}} {}{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ % }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{2.2763pt}\pgfsys@lineto{-2.2763pt}{-2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{-2.2763pt}\pgfsys@lineto{-2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{-2.2763pt}{-2.2763pt}\pgfsys@lineto{2.2763pt}{-2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{-2.2763pt}\pgfsys@lineto{2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope \pgfsys@invoke{ }\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{% }\pgfsys@endscope\hss}}\endpgfpicture}},\hbox to4.95pt{\vbox to4.95pt{% \pgfpicture\makeatletter\hbox{\>\lower-2.4763pt\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{\the\pgflinewidth}\pgfsys@invoke{ }% \nullfont\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}} {}{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ % }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{2.2763pt}\pgfsys@lineto{-2.2763pt}{-2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{-2.2763pt}\pgfsys@lineto{-2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope {{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{2.2763pt}\pgfsys@lineto{-2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope \pgfsys@invoke{ }\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{% }\pgfsys@endscope\hss}}\endpgfpicture}},\hbox to4.95pt{\vbox to4.95pt{% \pgfpicture\makeatletter\hbox{\>\lower-2.4763pt\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{\the\pgflinewidth}\pgfsys@invoke{ }% \nullfont\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}} {}{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ % }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{2.2763pt}\pgfsys@lineto{-2.2763pt}{-2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{-2.2763pt}\pgfsys@lineto{-2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope \pgfsys@invoke{ }\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{% }\pgfsys@endscope\hss}}\endpgfpicture}}\}\neq\emptyset$ deciding geometric $\mathcal{S}$ -restricted $1$ -planarity and $\mathcal{S}$ -restricted $1$ -planarity is $\mathsf{NP}$ -complete and para- $\mathsf{NP}$ -hard when parameterized by the pathwidth.

$\mathsf{NP}$ membership follows due to the fact that geometric 1-planar graphs are characterized by having drawings without B- and W-configurations. For $\mathsf{NP}$ -hardness, we show for every singleton $\mathcal{S}^{\prime}\subset\{\hbox to4.95pt{\vbox to4.95pt{\pgfpicture% \makeatletter\hbox{\>\lower-2.4763pt\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{\the\pgflinewidth}\pgfsys@invoke{ }% \nullfont\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}} {}{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ % }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{2.2763pt}\pgfsys@lineto{-2.2763pt}{-2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{-2.2763pt}\pgfsys@lineto{-2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{-2.2763pt}{-2.2763pt}\pgfsys@lineto{2.2763pt}{-2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{-2.2763pt}\pgfsys@lineto{2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope \pgfsys@invoke{ }\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{% }\pgfsys@endscope\hss}}\endpgfpicture}},\hbox to4.95pt{\vbox to4.95pt{% \pgfpicture\makeatletter\hbox{\>\lower-2.4763pt\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{\the\pgflinewidth}\pgfsys@invoke{ }% \nullfont\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}} {}{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ % }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{2.2763pt}\pgfsys@lineto{-2.2763pt}{-2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{-2.2763pt}\pgfsys@lineto{-2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope {{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{2.2763pt}\pgfsys@lineto{-2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope \pgfsys@invoke{ }\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{% }\pgfsys@endscope\hss}}\endpgfpicture}},\hbox to4.95pt{\vbox to4.95pt{% \pgfpicture\makeatletter\hbox{\>\lower-2.4763pt\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{\the\pgflinewidth}\pgfsys@invoke{ }% \nullfont\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}} {}{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ % }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{2.2763pt}\pgfsys@lineto{-2.2763pt}{-2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{-2.2763pt}\pgfsys@lineto{-2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope \pgfsys@invoke{ }\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{% }\pgfsys@endscope\hss}}\endpgfpicture}}\}$ how to transform any 3-Partition instance $I$ into a graph with constant pathwidth that is geometric $\mathcal{S}^{\prime}$ -restricted $1$ -planar if $I$ is a yes-instance and not even $1$ -planar if $I$ is a no-instance. This then directly yields a reduction from 3-Partition to recognizing $\mathcal{S}$ -restricted $1$ -planarity and geometric $\mathcal{S}$ -restricted $1$ -planarity for any $\mathcal{S}$ with $\mathcal{S}\cap\{\hbox to4.95pt{\vbox to4.95pt{\pgfpicture\makeatletter\hbox{% \>\lower-2.4763pt\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{\the% \pgflinewidth}\pgfsys@invoke{ }\nullfont\hbox to0.0pt{\pgfsys@beginscope% \pgfsys@invoke{ }{{}} {}{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ % }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{2.2763pt}\pgfsys@lineto{-2.2763pt}{-2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{-2.2763pt}\pgfsys@lineto{-2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{-2.2763pt}{-2.2763pt}\pgfsys@lineto{2.2763pt}{-2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{-2.2763pt}\pgfsys@lineto{2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope \pgfsys@invoke{ }\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{% }\pgfsys@endscope\hss}}\endpgfpicture}},\hbox to4.95pt{\vbox to4.95pt{% \pgfpicture\makeatletter\hbox{\>\lower-2.4763pt\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{\the\pgflinewidth}\pgfsys@invoke{ }% \nullfont\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}} {}{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ % }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{2.2763pt}\pgfsys@lineto{-2.2763pt}{-2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{-2.2763pt}\pgfsys@lineto{-2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope {{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{2.2763pt}\pgfsys@lineto{-2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope \pgfsys@invoke{ }\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{% }\pgfsys@endscope\hss}}\endpgfpicture}},\hbox to4.95pt{\vbox to4.95pt{% \pgfpicture\makeatletter\hbox{\>\lower-2.4763pt\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{\the\pgflinewidth}\pgfsys@invoke{ }% \nullfont\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}} {}{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ % }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{2.2763pt}\pgfsys@lineto{-2.2763pt}{-2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{-2.2763pt}\pgfsys@lineto{-2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope \pgfsys@invoke{ }\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{% }\pgfsys@endscope\hss}}\endpgfpicture}}\}\neq\emptyset$ .

Our transformation builds upon Grigoriev and Bodlaender’s proof that determining $1$ -planarity is NP-complete [16]. We provide the reduction in detail, as it showcases the main ideas, and refer to the full version for complete proofs.

The problem 3-Partition is given a set $A$ of $3m$ elements with $m\geq 3$ , a bound $B\in\mathbb{Z}^{+}$ , and a size $s(a)\in\mathbb{Z}^{+}$ for each $a\in A$ such that $\sum_{a\in A}s(a)=mB$ , and asks whether $A$ can be partitioned into $m$ disjoint subsets $A_{1},\dots,A_{m}$ of size three such that for $1\leq i\leq m$ we have $\sum_{a\in A_{i}}s(a)=B$ . As 3-Partition is strongly NP-complete, we can assume that $B$ is polynomial in $m$ . For convenience, we furthermore assume for $\mathcal{S}^{\prime}=\{\hbox to4.95pt{\vbox to4.95pt{\pgfpicture\makeatletter% \hbox{\>\lower-2.4763pt\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{\the\pgflinewidth}\pgfsys@invoke{ }\nullfont\hbox to0.0pt% {\pgfsys@beginscope\pgfsys@invoke{ }{{}} {}{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ % }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{2.2763pt}\pgfsys@lineto{-2.2763pt}{-2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{-2.2763pt}\pgfsys@lineto{-2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope {{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{2.2763pt}\pgfsys@lineto{-2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope \pgfsys@invoke{ }\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{% }\pgfsys@endscope\hss}}\endpgfpicture}}\}$ that both $B$ and $m$ are even.

Figure 4: (left) Fence

F_{u,v}

between nodes

u

and

v

. The single edges are thick; the direct edges whose presence depends on

\mathcal{S}^{\prime}

are dashed. (right) Example of how a splitter edge (blue) crosses a rim edge. All three crossings are -crossings.

Before we describe the transformation itself, we construct what we call fences. For any two nodes $u$ and $v$ , the fence $F_{u,v}$ between them is constructed as follows (see the left side of Figure 4 for reference): We start with a $K_{5}$ on $u$ , $v$ and three new nodes $w_{1}$ , $w_{2}$ , $w_{3}$ . Next we replace all of its edges other than $uw_{2}$ and $vw_{1}$ by a bundle of $\ell=12$ parallel paths of length two. We call $uw_{2}$ and $vw_{1}$ the single edges of the fence. For $\mathcal{S}^{\prime}=\{\hbox to4.95pt{\vbox to4.95pt{\pgfpicture\makeatletter% \hbox{\>\lower-2.4763pt\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{\the\pgflinewidth}\pgfsys@invoke{ }\nullfont\hbox to0.0pt% {\pgfsys@beginscope\pgfsys@invoke{ }{{}} {}{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ % }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{2.2763pt}\pgfsys@lineto{-2.2763pt}{-2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{-2.2763pt}\pgfsys@lineto{-2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{-2.2763pt}{-2.2763pt}\pgfsys@lineto{2.2763pt}{-2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{-2.2763pt}\pgfsys@lineto{2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope \pgfsys@invoke{ }\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{% }\pgfsys@endscope\hss}}\endpgfpicture}}\}$ we re-add the edges $u v$ and $uw_{1}$ and for $\mathcal{S}^{\prime}=\{\hbox to4.95pt{\vbox to4.95pt{\pgfpicture\makeatletter% \hbox{\>\lower-2.4763pt\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{\the\pgflinewidth}\pgfsys@invoke{ }\nullfont\hbox to0.0pt% {\pgfsys@beginscope\pgfsys@invoke{ }{{}} {}{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ % }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{2.2763pt}\pgfsys@lineto{-2.2763pt}{-2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{-2.2763pt}\pgfsys@lineto{-2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope {{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{2.2763pt}\pgfsys@lineto{-2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope \pgfsys@invoke{ }\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{% }\pgfsys@endscope\hss}}\endpgfpicture}}\}$ we re-add either the edge $u v$ or $uw_{1}$ (details follow later). This ensures that the crossing between the single edges is an $\mathcal{S}^{\prime}$ -crossing. The drawings depicted in the left side of Figure 4 shows a geometric $\mathcal{S}$ -restricted $1$ -planar drawing of a fence where $u$ and $v$ share a face. The following lemma shows that we can treat fences as uncrossable edges in the context of $1$ -planar drawings.

Lemma 18.

Let $G=(V,E)$ be a $1$ -planar graph and $u,v\in V$ be two nodes between which there is a fence $F_{u,v}\subseteq G$ . Then in every $1$ -planar drawing $\Gamma$ of $G$ , the single edges of $F_{u,v}$ cross (and whereby $u$ and $v$ share a face).

Figure 5: Graph

G_{I}

based on 3-Partition Instance

I

with

A=\{1,2,2,2,3,3,3,4,4\}

,

B=10

, and

m=3

. The fences have a fence pattern, the wheels are red, the splitters are blue, and the dividers are gray. A Kuratowski subdivision of interest is highlighted in yellow.

Given a 3-Partition instance $I$ we construct a graph $G_{I}$ as follows (see also Figure 5): We start with two wheels with fences as radians; one of size $3m$ , the transmitter, and one of size $B m$ , the collector. For $\mathcal{S}^{\prime}=\{\hbox to4.95pt{\vbox to4.95pt{\pgfpicture\makeatletter% \hbox{\>\lower-2.4763pt\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{\the\pgflinewidth}\pgfsys@invoke{ }\nullfont\hbox to0.0pt% {\pgfsys@beginscope\pgfsys@invoke{ }{{}} {}{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ % }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{{}}\pgfsys@beginscope\pgfsys@invoke{ }% \pgfsys@roundcap\pgfsys@invoke{ }{}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{% {\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{2.2763pt}\pgfsys@lineto{-2.2763pt}{-2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope{{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{-2.2763pt}\pgfsys@lineto{-2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope {{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{ }{}% \pgfsys@moveto{2.2763pt}{2.2763pt}\pgfsys@lineto{-2.2763pt}{2.2763pt}% \pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope \pgfsys@invoke{ }\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{% }\pgfsys@endscope\hss}}\endpgfpicture}}\}$ every even-numbered radian fence has the edge $u v$ and every odd-numbered has $uw_{1}$ . Next, we add a path of three fences between the $3i$ -th node of the transmitter and the $B i$ -th node of the collector for $1\leq i\leq m$ . We call the resulting $m$ paths of fences between the wheel centers dividers. For each element $a\in A$ we add a splitter $Q_{a}$ , which consists of a claw of size $s(a)$ of fences and an edge between every degree- $1$ node of the claw and the collector center and an edge between the degree- $s(a)$ node of the claw and the transmitter center. One can show that $I$ can be satisfyingly partitioned if and only if $G_{I}$ is geometric $\mathcal{S}^{\prime}$ -restricted $1$ -planar. Moreover, the graph $G_{I}$ has constant pathwidth. This leads to Theorem 17.

References

[1] Michael J. Bannister, Sergio Cabello, and David Eppstein. Parameterized complexity of 1-planarity. J. Graph Algorithms Appl., 22(1):23–49, 2018. doi:10.7155/JGAA.00457.
[2] Giuseppe Di Battista and Roberto Tamassia. Incremental planarity testing (extended abstract). In 30th Annual Symposium on Foundations of Computer Science, pages 436–441. IEEE Computer Society, 1989. doi:10.1109/SFCS.1989.63515.
[3] Therese Biedl, Prosenjit Bose, and Karthik Murali. A parameterized algorithm for vertex and edge connectivity of embedded graphs. In 32nd Annual European Symposium on Algorithms, ESA 2024, volume 308 of LIPIcs, pages 24:1–24:15, 2024. doi:10.4230/LIPICS.ESA.2024.24.
[4] Therese Biedl and Karthik Murali. On computing the vertex connectivity of 1-plane graphs. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023), volume 261 of LIPIcs, pages 23:1–23:16, 2023. doi:10.4230/LIPIcs.ICALP.2023.23.
[5] Daniel Bienstock and Nathaniel Dean. Bounds for rectilinear crossing numbers. J. Graph Theory, 17(3):333–348, 1993. doi:10.1002/JGT.3190170308.
[6] Hans L. Bodlaender. A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput., 25(6):1305–1317, 1996. doi:10.1137/S0097539793251219.
[7] Prosenjit Bose, Jean-Lou De Carufel, Anil Maheshwari, and Karthik Murali. On 1-planar graphs with bounded cop-number. Theor. Comput. Sci., 1037:115160, 2025. doi:10.1016/J.TCS.2025.115160.
[8] Franz J. Brandenburg. On 4-map graphs and 1-planar graphs and their recognition problem. CoRR, abs/1509.03447, 2015. arXiv:1509.03447.
[9] Sergio Cabello and Bojan Mohar. Adding one edge to planar graphs makes crossing number and 1-planarity hard. SIAM J. Comput., 42(5):1803–1829, 2013. doi:10.1137/120872310.
[10] Bruno Courcelle. The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Inform. and Comput., 85(1):12–75, 1990. doi:10.1016/0890-5401(90)90043-H.
[11] Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. doi:10.1007/978-3-319-21275-3.
[12] Walter Didimo, Giuseppe Liotta, and Fabrizio Montecchiani. A survey on graph drawing beyond planarity. ACM Comput. Surv., 52(1):4:1–4:37, 2019. doi:10.1145/3301281.
[13] Reinhard Diestel. Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics. Springer, 2012.
[14] Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. doi:10.1007/978-1-4471-5559-1.
[15] István Fáry. On straight-line representation of planar graphs. Acta Sci. Math. (Szeged), 11:229–233, 1948.
[16] Alexander Grigoriev and Hans L. Bodlaender. Algorithms for graphs embeddable with few crossings per edge. Algorithmica, 49(1):1–11, 2007. doi:10.1007/S00453-007-0010-X.
[17] Martin Grohe. Computing crossing numbers in quadratic time. J. Comput. Syst. Sci., 68(2):285–302, 2004. doi:10.1016/J.JCSS.2003.07.008.
[18] Carsten Gutwenger and Petra Mutzel. A linear time implementation of SPQR-trees. In Graph Drawing, 8th International Symposium, GD 2000, volume 1984 of Lecture Notes in Computer Science, pages 77–90, 2000. doi:10.1007/3-540-44541-2_8.
[19] Thekla Hamm and Petr Hlinený. Parameterised partially-predrawn crossing number. In 38th International Symposium on Computational Geometry, SoCG 2022, volume 224 of LIPIcs, pages 46:1–46:15, 2022. doi:10.4230/LIPICS.SOCG.2022.46.
[20] Seok-Hee Hong, Peter Eades, Giuseppe Liotta, and Sheung-Hung Poon. Fáry’s theorem for 1-planar graphs. In Computing and Combinatorics - 18th Annual International Conference, COCOON 2012, volume 7434 of Lecture Notes in Computer Science, pages 335–346, 2012. doi:10.1007/978-3-642-32241-9_29.
[21] Seok-Hee Hong and Takeshi Tokuyama, editors. Beyond Planar Graphs, Communications of NII Shonan Meetings. Springer, 2020. doi:10.1007/978-981-15-6533-5.
[22] Stephen G. Kobourov, Giuseppe Liotta, and Fabrizio Montecchiani. An annotated bibliography on 1-planarity. Comput. Sci. Rev., 25:49–67, 2017. doi:10.1016/J.COSREV.2017.06.002.
[23] Vladimir P. Korzhik and Bojan Mohar. Minimal obstructions for 1-immersions and hardness of 1-planarity testing. J. Graph Theory, 72(1):30–71, 2013. doi:10.1002/JGT.21630.
[24] Kazimierz Kuratowski. Sur le probleme des courbes gauches en topologie. Fundamenta mathematicae, 15(1):271–283, 1930.
[25] Bojan Mohar and Carsten Thomassen. Graphs on surfaces. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, Baltimore, MD, 2001.
[26] Miriam Münch and Ignaz Rutter. Parameterized algorithms for beyond-planar crossing numbers. In 32nd International Symposium on Graph Drawing and Network Visualization, GD 2024, volume 320 of LIPIcs, pages 25:1–25:16, 2024. doi:10.4230/LIPICS.GD.2024.25.
[27] Carsten Thomassen. Rectilinear drawings of graphs. J. Graph Theory, 12(3):335–341, 1988. doi:10.1002/JGT.3190120306.
[28] Klaus Wagner. Bemerkungen zum Vierfarbenproblem. Jahresbericht der Deutschen Mathematiker-Vereinigung, 46:26–32, 1936.
[29] Meirav Zehavi. Parameterized analysis and crossing minimization problems. Comput. Sci. Rev., 45:100490, 2022. doi:10.1016/J.COSREV.2022.100490.

[bib.bib1] [1] Michael J. Bannister, Sergio Cabello, and David Eppstein. Parameterized complexity of 1-planarity. J. Graph Algorithms Appl., 22(1):23–49, 2018. doi:10.7155/JGAA.00457.

[bib.bib2] [2] Giuseppe Di Battista and Roberto Tamassia. Incremental planarity testing (extended abstract). In 30th Annual Symposium on Foundations of Computer Science, pages 436–441. IEEE Computer Society, 1989. doi:10.1109/SFCS.1989.63515.

[bib.bib3] [3] Therese Biedl, Prosenjit Bose, and Karthik Murali. A parameterized algorithm for vertex and edge connectivity of embedded graphs. In 32nd Annual European Symposium on Algorithms, ESA 2024, volume 308 of LIPIcs, pages 24:1–24:15, 2024. doi:10.4230/LIPICS.ESA.2024.24.

[bib.bib4] [4] Therese Biedl and Karthik Murali. On computing the vertex connectivity of 1-plane graphs. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023), volume 261 of LIPIcs, pages 23:1–23:16, 2023. doi:10.4230/LIPIcs.ICALP.2023.23.

[bib.bib5] [5] Daniel Bienstock and Nathaniel Dean. Bounds for rectilinear crossing numbers. J. Graph Theory, 17(3):333–348, 1993. doi:10.1002/JGT.3190170308.

[bib.bib6] [6] Hans L. Bodlaender. A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput., 25(6):1305–1317, 1996. doi:10.1137/S0097539793251219.

[bib.bib7] [7] Prosenjit Bose, Jean-Lou De Carufel, Anil Maheshwari, and Karthik Murali. On 1-planar graphs with bounded cop-number. Theor. Comput. Sci., 1037:115160, 2025. doi:10.1016/J.TCS.2025.115160.

[bib.bib8] [8] Franz J. Brandenburg. On 4-map graphs and 1-planar graphs and their recognition problem. CoRR, abs/1509.03447, 2015. arXiv:1509.03447.

[bib.bib9] [9] Sergio Cabello and Bojan Mohar. Adding one edge to planar graphs makes crossing number and 1-planarity hard. SIAM J. Comput., 42(5):1803–1829, 2013. doi:10.1137/120872310.

[bib.bib10] [10] Bruno Courcelle. The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Inform. and Comput., 85(1):12–75, 1990. doi:10.1016/0890-5401(90)90043-H.

[bib.bib11] [11] Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. doi:10.1007/978-3-319-21275-3.

[bib.bib12] [12] Walter Didimo, Giuseppe Liotta, and Fabrizio Montecchiani. A survey on graph drawing beyond planarity. ACM Comput. Surv., 52(1):4:1–4:37, 2019. doi:10.1145/3301281.

[bib.bib13] [13] Reinhard Diestel. Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics. Springer, 2012.

[bib.bib14] [14] Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. doi:10.1007/978-1-4471-5559-1.

[bib.bib15] [15] István Fáry. On straight-line representation of planar graphs. Acta Sci. Math. (Szeged), 11:229–233, 1948.

[bib.bib16] [16] Alexander Grigoriev and Hans L. Bodlaender. Algorithms for graphs embeddable with few crossings per edge. Algorithmica, 49(1):1–11, 2007. doi:10.1007/S00453-007-0010-X.

[bib.bib17] [17] Martin Grohe. Computing crossing numbers in quadratic time. J. Comput. Syst. Sci., 68(2):285–302, 2004. doi:10.1016/J.JCSS.2003.07.008.

[bib.bib18] [18] Carsten Gutwenger and Petra Mutzel. A linear time implementation of SPQR-trees. In Graph Drawing, 8th International Symposium, GD 2000, volume 1984 of Lecture Notes in Computer Science, pages 77–90, 2000. doi:10.1007/3-540-44541-2_8.

[bib.bib19] [19] Thekla Hamm and Petr Hlinený. Parameterised partially-predrawn crossing number. In 38th International Symposium on Computational Geometry, SoCG 2022, volume 224 of LIPIcs, pages 46:1–46:15, 2022. doi:10.4230/LIPICS.SOCG.2022.46.

[bib.bib20] [20] Seok-Hee Hong, Peter Eades, Giuseppe Liotta, and Sheung-Hung Poon. Fáry’s theorem for 1-planar graphs. In Computing and Combinatorics - 18th Annual International Conference, COCOON 2012, volume 7434 of Lecture Notes in Computer Science, pages 335–346, 2012. doi:10.1007/978-3-642-32241-9_29.

[bib.bib21] [21] Seok-Hee Hong and Takeshi Tokuyama, editors. Beyond Planar Graphs, Communications of NII Shonan Meetings. Springer, 2020. doi:10.1007/978-981-15-6533-5.

[bib.bib22] [22] Stephen G. Kobourov, Giuseppe Liotta, and Fabrizio Montecchiani. An annotated bibliography on 1-planarity. Comput. Sci. Rev., 25:49–67, 2017. doi:10.1016/J.COSREV.2017.06.002.

[bib.bib23] [23] Vladimir P. Korzhik and Bojan Mohar. Minimal obstructions for 1-immersions and hardness of 1-planarity testing. J. Graph Theory, 72(1):30–71, 2013. doi:10.1002/JGT.21630.

[bib.bib24] [24] Kazimierz Kuratowski. Sur le probleme des courbes gauches en topologie. Fundamenta mathematicae, 15(1):271–283, 1930.

[bib.bib25] [25] Bojan Mohar and Carsten Thomassen. Graphs on surfaces. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, Baltimore, MD, 2001.

[bib.bib26] [26] Miriam Münch and Ignaz Rutter. Parameterized algorithms for beyond-planar crossing numbers. In 32nd International Symposium on Graph Drawing and Network Visualization, GD 2024, volume 320 of LIPIcs, pages 25:1–25:16, 2024. doi:10.4230/LIPICS.GD.2024.25.

[bib.bib27] [27] Carsten Thomassen. Rectilinear drawings of graphs. J. Graph Theory, 12(3):335–341, 1988. doi:10.1002/JGT.3190120306.

[bib.bib28] [28] Klaus Wagner. Bemerkungen zum Vierfarbenproblem. Jahresbericht der Deutschen Mathematiker-Vereinigung, 46:26–32, 1936.

[bib.bib29] [29] Meirav Zehavi. Parameterized analysis and crossing minimization problems. Comput. Sci. Rev., 45:100490, 2022. doi:10.1016/J.COSREV.2022.100490.

A Dichotomy for 1-Planarity with Restricted Crossing Types Parameterized by Treewidth

Abstract

Keywords and phrases:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Acknowledgements:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

Our contribution.

Techniques.

2 Preliminaries

Graph terminology.

Graph drawing.

Parameterized complexity.

3 Fixed-Parameter Tractable Cases by Treewidth

Theorem 1.

Theorem 2.

3.1 Reducing to Internally 3-Connected Instances

Theorem 3.

Lemma 4.

Theorem 5.

Proof sketch.

3.2 An MSO-Encoding

3.2.1 Identifying planarized crossings

Lemma 6.

Definition 7 (chord description).

Lemma 8.

Proof.

Lemma 9.

Proof.

Building an MSO2-formula.

Lemma 10.

Corollary 11.

3.2.2 Encoding Straightline Planarity

Definition 12.

Observation 13.

Proof.

Lemma 14.

Proof.

Lemma 15.

Lemma 16.

4 Hard Cases for Constant Pathwidth

Theorem 17.

Lemma 18.

References

Building an MSO₂-formula.