Obtaining a Planar Graph by Vertex Deletion

DOI10.1007/978-3-540-74839-7_28zbMath1141.68542OpenAlexW2571453178MaRDI QIDQ3508576

Ildikó Schlotter, Dániel Marx

Publication date: 1 July 2008

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-74839-7_28

Mathematics Subject Classification ID

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)

Related Items (11)

Parameterized Graph Cleaning Problems ⋮ Contracting graphs to paths and trees ⋮ Minimum Fill-In and Treewidth of Split+ ke and Split+ kv Graphs ⋮ MSOL restricted contractibility to planar graphs ⋮ Parameterized graph cleaning problems ⋮ Minimum fill-in and treewidth of split \(+ ke\) and split \(+kv\) graphs ⋮ Chordal deletion is fixed-parameter tractable ⋮ Parameterizing above or below guaranteed values ⋮ A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems ⋮ Parameterized Complexity of Vertex Deletion into Perfect Graph Classes ⋮ Dynamically maintaining split graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graph minors. XX: Wagner's conjecture
• The node-deletion problem for hereditary properties is NP-complete
• Quickly excluding a planar graph
• 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
• Query evaluation via tree-decompositions
• 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
• Handbook of Graph Grammars and Computing by Graph Transformation
• Subgraph Isomorphism in Planar Graphs and Related Problems
• 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