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

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

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.

• Jezik: Angleški jezik
• Ključne besede: 1-planar, crossing type, treewidth, pathwidth
• Vrsta gradiva: Članek v reviji
• Tipologija: 1.08 - Objavljeni znanstveni prispevek na konferenci
• Organizacija: FMF - Fakulteta za matematiko in fiziko ; FRI - Fakulteta za računalništvo in informatiko
• Status publikacije: Objavljeno
• Različica publikacije: Objavljena publikacija
• Leto izida: 2025
• Št. strani: 15 str.
• PID: 20.500.12556/RUL-177822
• UDK: 004.42:519.17
• DOI: 10.4230/LIPIcs.ISAAC.2025.16
• COBISS.SI-ID: 263974915
• Datum objave v RUL: 08.01.2026

Gradivo je del monografije

• Naslov: 36th International Symposium on Algorithms and Computation : ISAAC 2025, December 7-10, 2025, Tainan, Taiwan
• Uredniki: Ho-Lin Chen, Wing-Kai Hon, Meng-Tsung Tsai
• Kraj izida: Saarbrücken/Wadern
• Založnik: Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing
• Leto izida: 2025
• ISBN: 978-3-95977-408-6
• COBISS.SI-ID: 263944195
• Naslov zbirke: Leibniz international proceedings in informatics
• Številčenje v zbirki: ǂvol. ǂ359
• ISSN zbirke: 1868-8969

Licence

• Licenca: CC BY 4.0, Creative Commons Priznanje avtorstva 4.0 Mednarodna
• Povezava: http://creativecommons.org/licenses/by/4.0/deed.sl
• Opis: To je standardna licenca Creative Commons, ki daje uporabnikom največ možnosti za nadaljnjo uporabo dela, pri čemer morajo navesti avtorja.