A Near-Optimal Planarization Algorithm

DOI10.1137/1.9781611973402.130zbMath1423.68341OpenAlexW4213262063MaRDI QIDQ5384092

Saket Saurabh, Daniel Lokshtanov, Bart M. P. Jansen

Publication date: 20 June 2019

Published in: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/1.9781611973402.130

Mathematics Subject Classification ID

Analysis of algorithms (68W40) 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)

Related Items (28)

Linear Time Parameterized Algorithms for Subset Feedback Vertex Set ⋮ Faster FPT algorithms for deletion to pairs of graph classes ⋮ Distance from triviality 2.0: hybrid parameterizations ⋮ A tight lower bound for vertex planarization on graphs of bounded treewidth ⋮ Hitting forbidden subgraphs in graphs of bounded treewidth ⋮ \(k\)-apices of minor-closed graph classes. I: Bounding the obstructions ⋮ Polynomial Kernel for Interval Vertex Deletion ⋮ Deletion to scattered graph classes. II: Improved FPT algorithms for deletion to pairs of graph classes ⋮ Hitting Minors on Bounded Treewidth Graphs. IV. An Optimal Algorithm ⋮ Unnamed Item ⋮ Planarizing graphs and their drawings by vertex splitting ⋮ Recognizing map graphs of bounded treewidth ⋮ Hitting Minors on Bounded Treewidth Graphs. I. General Upper Bounds ⋮ A Deterministic Polynomial Kernel for Odd Cycle Transversal and Vertex Multiway Cut in Planar Graphs ⋮ Paths to trees and cacti ⋮ Unnamed Item ⋮ On the number of labeled graphs of bounded treewidth ⋮ Unnamed Item ⋮ A single-exponential FPT algorithm for the \(K_4\)-\textsc{minor cover} problem ⋮ Hitting minors on bounded treewidth graphs. III. Lower bounds ⋮ Hitting forbidden induced subgraphs on bounded treewidth graphs ⋮ A deterministic polynomial kernel for odd cycle transversal and vertex multiway cut in planar graphs ⋮ Hitting Forbidden Induced Subgraphs on Bounded Treewidth Graphs ⋮ Modification to Planarity is Fixed Parameter Tractable ⋮ Unnamed Item ⋮ Deleting vertices to graphs of bounded genus ⋮ A Linear-Time Parameterized Algorithm for Node Unique Label Cover ⋮ Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable

This page was built for publication: A Near-Optimal Planarization Algorithm