Obtaining a planar graph by vertex deletion

DOI10.1007/s00453-010-9484-zzbMath1239.05044OpenAlexW1495415187MaRDI QIDQ2429328

Dániel Marx, Ildikó Schlotter

Publication date: 26 April 2012

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-010-9484-z

zbMATH Keywords

planar graphFPT algorithmvertex deletionapex graph

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (26)

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 ⋮ Parameterized complexity of vertex deletion into perfect graph classes ⋮ \(k\)-apices of minor-closed graph classes. I: Bounding the obstructions ⋮ Combing a Linkage in an Annulus ⋮ Splitting plane graphs to outerplanarity ⋮ Sublinear approximation algorithms for boxicity and related problems ⋮ Parameterized complexity of finding connected induced subgraphs ⋮ Unnamed Item ⋮ Planarizing graphs and their drawings by vertex splitting ⋮ Proper interval vertex deletion ⋮ Contracting graphs to paths and trees ⋮ A faster FPT algorithm for bipartite contraction ⋮ All minor-minimal apex obstructions with connectivity two ⋮ Quadratic vertex kernel for split vertex deletion ⋮ The critical node detection problem in networks: a survey ⋮ 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 ⋮ Improved kernel and algorithm for claw and diamond free edge deletion based on refined observations ⋮ Modifying a graph using vertex elimination ⋮ Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable ⋮ Faster parameterized algorithms for deletion to split graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding odd cycle transversals.
• Graph minors. XX: Wagner's conjecture
• Chordal deletion is fixed-parameter tractable
• Graph minors. V. Excluding a planar graph
• The node-deletion problem for hereditary properties is NP-complete
• Quickly excluding a planar graph
• On search, decision, and the efficiency of polynomial-time algorithms
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Computing crossing numbers in quadratic time
• Graph minors. XIII: The disjoint paths problem
• The graph genus problem is NP-complete
• Crossing Number is NP-Complete
• Wheel-Free Deletion Is W[2-Hard]
• Applications of a Planar Separator Theorem
• Efficient Planarity Testing
• Finding a Maximum Cut of a Planar Graph in Polynomial Time
• Approximation algorithms for NP-complete problems on planar graphs
• ON DISJOINT CYCLES
• Subgraph Isomorphism in Planar Graphs and Related Problems
• Planarity Allowing Few Error Vertices in Linear Time
• AN IMPROVED ALGORITHM FOR FINDING TREE DECOMPOSITIONS OF SMALL WIDTH
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth

This page was built for publication: Obtaining a planar graph by vertex deletion