2026-06-09T12:33:48Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24924 2026-02-09T08:02:08Z ddc:004 open_access

A Dichotomy for 1-Planarity with Restricted Crossing Types Parameterized by Treewidth Cabello, Sergio Dobler, Alexander Fijavž, Gašper Hamm, Thekla Wagner, Mirko H. 1-planar crossing type treewidth pathwidth 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 𝒮 of crossing types gives a recognition problem: does a given graph admit an 𝒮-restricted drawing, that is, a 1-planar drawing where the crossing type of each crossing is in 𝒮? We show that there is a set 𝒮_bad with three crossing types and the following properties: - If 𝒮 contains no crossing type from 𝒮_bad, then the recognition of graphs that admit an 𝒮-restricted drawing is fixed-parameter tractable with respect to the treewidth of the input graph. - If 𝒮 contains any crossing type from 𝒮_bad, then it is NP-hard to decide whether a graph has an 𝒮-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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sergio Cabello and Alexander Dobler and Gašper Fijavž and Thekla Hamm and Mirko H. Wagner 2025 Is Part Of LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2025.16 urn:nbn:de:0030-drops-249248 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.16 eng https://creativecommons.org/licenses/by/4.0/legalcode