Parameterized complexity of 1-planarity
DOI10.7155/JGAA.00457zbMATH Open1377.05118OpenAlexW2772525715MaRDI QIDQ4600735FDOQ4600735
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)
Full work available at URL: https://doi.org/10.7155/jgaa.00457
Recommendations
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)
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 queue layouts
- Parameterized algorithms for book embedding problems
- 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
- Fixed-parameter algorithms for computing RAC drawings of graphs
- 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 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
- Grid recognition: classical and parameterized computational perspectives
- 1-planarity testing and embedding: an experimental study
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)