2026-08-08T07:00:21Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:21309 2024-10-28T09:51:05Z ddc:004 open_access

Parameterized Algorithms for Beyond-Planar Crossing Numbers Münch, Miriam Rutter, Ignaz FPT Beyond-planarity Crossing-number Crossing Patterns Beyond-planar graph classes are usually defined via forbidden configurations or patterns in a drawing. In this paper, we formalize these concepts on a combinatorial level and show that, for any fixed family ℱ of crossing patterns, deciding whether a given graph G admits a drawing that avoids all patterns in F and that has at most c crossings is FPT w.r.t. c. In particular, we show that for any fixed k, deciding whether a graph is k-planar, k-quasi-planar, fan-crossing, fan-crossing-free or min-k-planar, respectively, is FPT with respect to the corresponding beyond-planar crossing number. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Miriam Münch and Ignaz Rutter 2024 Is Part Of LIPIcs, Volume 320, 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.GD.2024.25 urn:nbn:de:0030-drops-213096 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2024.25 eng https://creativecommons.org/licenses/by/4.0/legalcode