Vi ser problemet med att hitta en 1-plansritning för en allmän graf, där en 1-plansritning är en ritning där varje kant deltar i högst en korsning. Eftersom detta problem är känt för att vara NP-hård undersöker vi den parameteriserade komplexiteten av problemet med avseende på vertex täcknummer, träddjup och cyklomatiskt tal. För dessa parametrar konstruerar vi fasta parameterdragbara algoritmer. Problemet är dock fortfarande NP-komplett för grafer med begränsad bandbredd, vägbredd eller trädbredd.
Men utan begränsning till bokritningar, beräkning lokal korsning nummer är NP-hård även för grafer av avgränsad trädbredd REF.
Parameterized Complexity of 1-Planarity
{'venue': 'J. Graph Algorithms and Applications 22 (1): 23-49, 2018', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}