Parameterized Complexity of 1-Planarity

Abstract

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.

WADS 2013

Cited by in corpus (9)

• A Survey on Graph Drawing Beyond Planarity
• Recognizing and Drawing IC-planar Graphs
• Recognizing Optimal 1-Planar Graphs in Linear Time
• Track Layouts, Layered Path Decompositions, and Leveled Planarity
• A Fixed-Parameter Algorithm for the Max-Cut Problem on Embedded 1-Planar Graphs
• A Reduction System for Optimal 1-Planar Graphs
• Fixed parameter tractability of crossing minimization of almost-trees
• Parameterized Approaches to Orthogonal Compaction
• Re-embedding a 1-Plane Graph into a Straight-line Drawing in Linear Time