Parameterized complexity of 1-planarity

DOI10.7155/JGAA.00457MaRDI QIDQ4600735zbMATH OpenOpenAlexFDO

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

Publication date 12 January 2018

Published in Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.7155/jgaa.00457

zbMATH Keywords

graph drawing

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62)

Recommendations

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

Cited in

(29)

• Orthogonal planarity testing of bounded treewidth graphs
• Vertex-bipartition: a unified approach for kernelization of graph linear layout problems parameterized by vertex cover
• Weak-dynamic coloring of graphs beyond-planarity
• Track layouts, layered path decompositions, and leveled planarity
• Crossing minimization for 1-page and 2-page drawings of graphs with bounded treewidth
• Edge Partitions and Visibility Representations of 1-planar Graphs
• Parameterized algorithms for book embedding problems
• Parameterized algorithms for queue layouts
• Testing gap \(k\)-planarity is NP-complete
• A Tipping Point for the Planarity of Small and Medium Sized Graphs
• Beyond planar graphs: introduction
• Algorithms for 1-Planar Graphs
• Parameterized algorithms for linear layouts of graphs with respect to the vertex cover number
• Fixed-parameter algorithms for computing RAC drawings of graphs
• Fixed-parameter tractability for book drawing with bounded number of crossings per edge
• Parameterized algorithms for book embedding problems
• Parameterized complexity of 1-planarity
• 1-planarity of graphs with a rotation system
• Fixed-parameter algorithms for computing bend-restricted RAC drawings of graphs
• Parameterized analysis and crossing minimization problems
• On quasi-planar graphs: clique-width and logical description
• An annotated bibliography on 1-planarity
• Fixed-parameter algorithms for the weighted max-cut problem on embedded 1-planar graphs
• Parameterized approaches to orthogonal compaction
• Quantitative restrictions on crossing patterns
• \(k\)-planar graphs
• Sketched representations and orthogonal planarity of bounded treewidth graphs
• 1-planarity testing and embedding: an experimental study
• Grid recognition: classical and parameterized computational perspectives

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 Q4600735)