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

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

Recommendations

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

Cited in

(48)

• Track layouts, layered path decompositions, and leveled planarity
• Testing gap \(k\)-planarity is NP-complete
• Orthogonal planarity testing of bounded treewidth graphs
• 1-planarity testing and embedding: an experimental study
• Parameterized algorithms for linear layouts of graphs with respect to the vertex cover number
• Fixed-parameter tractability for book drawing with bounded number of crossings per edge
• Parameterized analysis and crossing minimization problems
• On quasi-planar graphs: clique-width and logical description
• Parameterized algorithms for book embedding problems
• Sketched representations and orthogonal planarity of bounded treewidth graphs
• Fixed-parameter algorithms for the weighted max-cut problem on embedded 1-planar graphs
• An annotated bibliography on 1-planarity
• Parameterized complexity of 1-planarity
• Crossing minimization for 1-page and 2-page drawings of graphs with bounded treewidth
• Beyond planar graphs: introduction
• Quantitative restrictions on crossing patterns
• Algorithms for 1-Planar Graphs
• Edge Partitions and Visibility Representations of 1-planar Graphs
• \(k\)-planar graphs
• A Tipping Point for the Planarity of Small and Medium Sized Graphs
• Parameterized algorithms for queue layouts
• Parameterized algorithms for book embedding problems
• 1-planarity of graphs with a rotation system
• Weak-dynamic coloring of graphs beyond-planarity
• Grid recognition: classical and parameterized computational perspectives
• Parameterized approaches to orthogonal compaction
• Vertex-bipartition: a unified approach for kernelization of graph linear layout problems parameterized by vertex cover
• Fixed-parameter algorithms for computing RAC drawings of graphs
• Fixed-parameter algorithms for computing bend-restricted RAC drawings of graphs
• Routing few robots in a crowded network
• On computing vertex connectivity of 1-planar graphs
• Computing twin-width parameterized by the feedback edge number
• Computing twin-width parameterized by the feedback edge number and vertex integrity
• Parameterized algorithms for beyond-planar crossing numbers
• Parameterized approaches to orthogonal compaction
• Drawn tree decomposition: new approach for graph drawing problems
• The lower bound of the number of non-crossed edges in local maximal 1-plane graphs
• Exact and approximate k-planarity testing for maximal graphs of small pathwidth
• Twin-width meets feedback edges and vertex integrity
• Routing few robots in a crowded network
• Recognizing 2-layer and outer k-planar graphs
• Heuristics for exact 1-planarity testing
• OOPS: optimized one-planarity solver via SAT
• Structural parameterizations of k-planarity
• Structural parameterizations of \(k\)-planarity
• Heuristics for exact 1-planarity testing
• OOPS: optimized one-planarity solver via SAT
• A dichotomy for 1-planarity with restricted crossing types parameterized by treewidth

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)