2026-09-12T09:10:17Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25002 2026-09-05T19:01:58Z ddc:004 open_access

Structural Parameterizations of k-Planarity Gima, Tatsuya Kobayashi, Yasuaki Okada, Yuto 1-planar graphs local crossing number beyond planarity parameterized complexity kernelization The concept of k-planarity is extensively studied in the context of Beyond Planarity. A graph is k-planar if it admits a drawing in the plane in which each edge is crossed at most k times. The local crossing number of a graph is the minimum integer k such that it is k-planar. The problem of determining whether an input graph is 1-planar is known to be NP-complete even for near-planar graphs [Cabello and Mohar, SIAM J. Comput. 2013], that is, the graphs obtained from planar graphs by adding a single edge. Moreover, the local crossing number is hard to approximate within a factor 2 - ε for any ε > 0 [Urschel and Wellens, IPL 2021]. To address this computational intractability, Bannister, Cabello, and Eppstein [JGAA 2018] investigated the parameterized complexity of the case of k = 1, particularly focusing on structural parameterizations on input graphs, such as treedepth, vertex cover number, and feedback edge number. In this paper, we extend their approach by considering the general case k ≥ 1 and give (tight) parameterized upper and lower bound results. In particular, we strengthen the aforementioned lower bound results to subclasses of constant-treewidth graphs: we show that testing 1-planarity is NP-complete even for near-planar graphs with feedback vertex set number at most 3 and pathwidth at most 4, and the local crossing number is hard to approximate within any constant factor for graphs with feedback vertex set number at most 2. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Tatsuya Gima and Yasuaki Kobayashi and Yuto Okada 2025 Is Part Of LIPIcs, Volume 357, 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.GD.2025.16 urn:nbn:de:0030-drops-250021 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.16 eng https://creativecommons.org/licenses/by/4.0/legalcode