Parameterized Complexity of 1-Planarity

DOI10.7155/jgaa.00457zbMath1377.05118OpenAlexW2772525715MaRDI QIDQ4600735

Sergio Cabello, Michael J. Bannister, 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

zbMATH Keywords

graph drawing

Mathematics Subject Classification ID

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

Related Items

Parameterized Algorithms for Queue Layouts, 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, Crossing Minimization for 1-page and 2-page Drawings of Graphs with Bounded Treewidth, Parameterized analysis and crossing minimization problems, Weak-dynamic coloring of graphs beyond-planarity, Grid recognition: classical and parameterized computational perspectives, Parameterized approaches to orthogonal compaction, Parameterized algorithms for book embedding problems, Sketched representations and orthogonal planarity of bounded treewidth graphs, Parameterized Algorithms for Book Embedding Problems, Track layouts, layered path decompositions, and leveled planarity, Testing gap \(k\)-planarity is NP-complete, Orthogonal planarity testing of bounded treewidth graphs, Beyond Planar Graphs: Introduction, Quantitative Restrictions on Crossing Patterns, Algorithms for 1-Planar Graphs, Edge Partitions and Visibility Representations of 1-planar Graphs, $$\textit{\textbf{k}}$$-Planar Graphs, 1-planarity testing and embedding: an experimental study, A Tipping Point for the Planarity of Small and Medium Sized Graphs