Planarity Allowing Few Error Vertices in Linear Time
From MaRDI portal
Publication:5171202
DOI10.1109/FOCS.2009.45zbMath1292.68093OpenAlexW2168568667MaRDI QIDQ5171202
Publication date: 25 July 2014
Published in: 2009 50th Annual IEEE Symposium on Foundations of Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1109/focs.2009.45
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items
Linear Time Parameterized Algorithms for Subset Feedback Vertex Set ⋮ Graph Minors and Parameterized Algorithm Design ⋮ What’s Next? Future Directions in Parameterized Complexity ⋮ A tight lower bound for vertex planarization on graphs of bounded treewidth ⋮ \(k\)-apices of minor-closed graph classes. I: Bounding the obstructions ⋮ Combing a Linkage in an Annulus ⋮ Unnamed Item ⋮ Treetopes and their graphs ⋮ Planarizing graphs and their drawings by vertex splitting ⋮ Obtaining a planar graph by vertex deletion ⋮ A faster FPT algorithm for bipartite contraction ⋮ The Parameterized Complexity of Finding Point Sets with Hereditary Properties ⋮ A Deterministic Polynomial Kernel for Odd Cycle Transversal and Vertex Multiway Cut in Planar Graphs ⋮ Unnamed Item ⋮ A deterministic polynomial kernel for odd cycle transversal and vertex multiway cut in planar graphs ⋮ Modification to Planarity is Fixed Parameter Tractable ⋮ Deleting vertices to graphs of bounded genus ⋮ A Linear-Time Parameterized Algorithm for Node Unique Label Cover
