Obtaining a Planar Graph by Vertex Deletion
From MaRDI portal
Publication:3508576
DOI10.1007/978-3-540-74839-7_28zbMath1141.68542OpenAlexW2571453178MaRDI QIDQ3508576
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
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