2013 | OriginalPaper | Chapter
Parameterized Complexity of 1-Planarity
Authors : Michael J. Bannister, Sergio Cabello, David Eppstein
Published in: Algorithms and Data Structures
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We consider the problem of finding a 1-planar drawing for a general graph, where a 1-planar drawing is a drawing in which each edge participates in at most one crossing. Since this problem is known to be
NP
-hard we investigate the parameterized complexity of the problem with respect to the vertex cover number, tree-depth, and cyclomatic number. For these parameters we construct fixed-parameter tractable algorithms. However, the problem remains
NP
-complete for graphs of bounded bandwidth, pathwidth, or treewidth.