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)

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

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)