A dichotomy for 1-planarity with restricted crossing types parameterized by treewidth

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

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: (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.

• Language: English
• Keywords: 1-planar, crossing type, treewidth, pathwidth
• Work type: Article
• Typology: 1.08 - Published Scientific Conference Contribution
• Organization: FMF - Faculty of Mathematics and Physics; FRI - Faculty of Computer and Information Science
• Publication status: Published
• Publication version: Version of Record
• Year: 2025
• Number of pages: 15 str.
• PID: 20.500.12556/RUL-177822
• UDC: 004.42:519.17
• DOI: 10.4230/LIPIcs.ISAAC.2025.16
• COBISS.SI-ID: 263974915
• Publication date in RUL: 08.01.2026

Record is a part of a monograph

• Title: 36th International Symposium on Algorithms and Computation : ISAAC 2025, December 7-10, 2025, Tainan, Taiwan
• Editors: Ho-Lin Chen, Wing-Kai Hon, Meng-Tsung Tsai
• Place of publishing: Saarbrücken/Wadern
• Publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing
• Year: 2025
• ISBN: 978-3-95977-408-6
• COBISS.SI-ID: 263944195
• Collection title: Leibniz international proceedings in informatics
• Collection numbering: ǂvol. ǂ359
• Collection ISSN: 1868-8969

Licences

• License: CC BY 4.0, Creative Commons Attribution 4.0 International
• Link: http://creativecommons.org/licenses/by/4.0/
• Description: This is the standard Creative Commons license that gives others maximum freedom to do what they want with the work as long as they credit the author.