A dichotomy for 1-planarity with restricted crossing types parameterized by treewidthCabello, Sergio (Avtor) Dobler, Alexander (Avtor) Fijavž, Gašper (Avtor) Hamm, Thekla (Avtor) Wagner, Mirko H. (Avtor) 1-planarcrossing typetreewidthpathwidthA 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: (i) 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. (ii) 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.20252026-01-08 14:53:12Neznano25062sl