Obtaining a planar graph by vertex deletion
From MaRDI portal
Publication:2429328
DOI10.1007/S00453-010-9484-ZzbMATH Open1239.05044OpenAlexW1495415187MaRDI QIDQ2429328FDOQ2429328
Authors: 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
Recommendations
- Obtaining a Planar Graph by Vertex Deletion
- Decomposing a planar graph into degenerate graphs
- Quickly excluding a planar graph
- scientific article; zbMATH DE number 4068901
- Minimal elimination of planar graphs
- On cleaving a planar graph
- Planarizing graphs and their drawings by vertex splitting
- Modifying a graph using vertex elimination
- Deleting vertices from a 2-connected graph with preserving 2-connectedness
- Reducing the maximum degree of a graph by deleting vertices
Graph algorithms (graph-theoretic aspects) (05C85) Planar graphs; geometric and topological aspects of graph theory (05C10)
Cites Work
- Fixed-parameter tractability of graph modification problems for hereditary properties
- Applications of a Planar Separator Theorem
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Finding odd cycle transversals.
- Graph minors. XX: Wagner's conjecture
- The node-deletion problem for hereditary properties is NP-complete
- Graph minors. XIII: The disjoint paths problem
- Title not available (Why is that?)
- Efficient Planarity Testing
- Approximation algorithms for NP-complete problems on planar graphs
- ON DISJOINT CYCLES
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Graph minors. V. Excluding a planar graph
- Quickly excluding a planar graph
- Title not available (Why is that?)
- Crossing Number is NP-Complete
- The graph genus problem is NP-complete
- Chordal deletion is fixed-parameter tractable
- Title not available (Why is that?)
- An improved algorithm for finding tree decompositions of small width
- On search, decision, and the efficiency of polynomial-time algorithms
- Finding a Maximum Cut of a Planar Graph in Polynomial Time
- Title not available (Why is that?)
- Subgraph Isomorphism in Planar Graphs and Related Problems
- Title not available (Why is that?)
- Title not available (Why is that?)
- Computing crossing numbers in quadratic time
- Title not available (Why is that?)
- Title not available (Why is that?)
- Wheel-Free Deletion Is W[2]-Hard
- Planarity Allowing Few Error Vertices in Linear Time
Cited In (35)
- A faster FPT algorithm for bipartite contraction
- Parameterized complexity of vertex deletion into perfect graph classes
- The non planar vertex deletion of \(C_n\times C_m\).
- Modification to Planarity is Fixed Parameter Tractable
- All minor-minimal apex obstructions with connectivity two
- Parameterized complexity of finding connected induced subgraphs
- What's next? Future directions in parameterized complexity
- Planarizing graphs and their drawings by vertex splitting
- Sublinear approximation algorithms for boxicity and related problems
- Title not available (Why is that?)
- \(k\)-apices of minor-closed graph classes. I: Bounding the obstructions
- Graph minors and parameterized algorithm design
- Proper interval vertex deletion
- Modifying a graph using vertex elimination
- Fast partitioning \(l\)-apex graphs with applications to approximating maximum induced-subgraph problems
- Faster parameterized algorithms for modification problems to minor-closed classes
- Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable
- A more accurate view of the flat wall theorem
- Title not available (Why is that?)
- Quadratic vertex kernel for split vertex deletion
- Splitting plane graphs to outerplanarity
- A deterministic polynomial kernel for odd cycle transversal and vertex multiway cut in planar graphs
- Deleting vertices to graphs of bounded genus
- A Deterministic Polynomial Kernel for Odd Cycle Transversal and Vertex Multiway Cut in Planar Graphs
- Obtaining a Planar Graph by Vertex Deletion
- Combing a Linkage in an Annulus
- Faster parameterized algorithms for deletion to split graphs
- Splitting plane graphs to outerplanarity
- A tight lower bound for vertex planarization on graphs of bounded treewidth
- Lossy planarization: a constant-factor approximate kernelization for planar vertex deletion
- A near-optimal planarization algorithm
- Computing paths of large rank in planar frameworks deterministically
- Improved kernel and algorithm for claw and diamond free edge deletion based on refined observations
- The critical node detection problem in networks: a survey
- Contracting graphs to paths and trees
This page was built for publication: Obtaining a planar graph by vertex deletion
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2429328)
