Parameterized complexity of 1-planarity

DOI10.1007/978-3-642-40104-6_9MaRDI QIDQ2842148zbMATH OpenOpenAlexFDO

Authors Michael J. Bannister, S. Cabello, David Eppstein

Publication date 12 August 2013

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1304.5591

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

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.

Recommendations

• Parameterized complexity of 1-planarity
• 1-planarity of graphs with a rotation system
• 1-planarity testing and embedding: an experimental study

Cited in

(15)

• Recognizing optimal 1-planar graphs in linear time
• A linear-time algorithm for testing full outer-2-planarity
• On quasi-planar graphs: clique-width and logical description
• Fixed-parameter algorithms for the weighted max-cut problem on embedded 1-planar graphs
• Re-embedding a 1-plane graph for a straight-line drawing in linear time
• Remarks on the joins of 1-planar graphs
• Width, depth, and space: tradeoffs between branching and dynamic programming
• An annotated bibliography on 1-planarity
• \(\mathsf{NIC}\)-planar graphs
• Outer 1-planar graphs
• Track layout is hard
• A note on 1-planar graphs
• Recognizing IC-planar and NIC-planar graphs
• Parameterized complexity of 1-planarity
• A linear-time algorithm for testing outer-1-planarity

This page was built for publication: Parameterized complexity of 1-planarity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2842148)