{"ID":2840267,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.14975","arxiv_id":"2511.14975","title":"A Dichotomy for 1-Planarity with Restricted Crossing Types Parameterized by Treewidth","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: 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. 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.","short_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 t...","url_abs":"https://arxiv.org/abs/2511.14975","url_pdf":"https://arxiv.org/pdf/2511.14975v1","authors":"[\"Sergio Cabello\",\"Alexander Dobler\",\"Gašper Fijavž\",\"Thekla Hamm\",\"Mirko H. Wagner\"]","published":"2025-11-18T23:44:35Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.CG\",\"math.CO\"]","methods":"[]","has_code":false}