Obtaining planarity by contracting few edges
From MaRDI portal
Publication:1945931
DOI10.1016/j.tcs.2012.12.041zbMath1260.68156OpenAlexW1561738351MaRDI QIDQ1945931
Daniël Paulusma, Pim van 't Hof, Petr A. Golovach
Publication date: 17 April 2013
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2012.12.041
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) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (22)
Paths to Trees and Cacti ⋮ Efficient Graph Minors Theory and Parameterized Algorithms for (Planar) Disjoint Paths ⋮ On the parameterized complexity of maximum degree contraction problem ⋮ Graph editing to a fixed target ⋮ The complexity of degree anonymization by graph contractions ⋮ On the parameterized complexity of grid contraction ⋮ Reducing the vertex cover number via edge contractions ⋮ Obtaining split graphs by edge contraction ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ Unnamed Item ⋮ A single exponential-time FPT algorithm for cactus contraction ⋮ Parameterized complexity of three edge contraction problems with degree constraints ⋮ Contracting to a longest path in H-free graphs ⋮ On the Parameterized Complexity of Maximum Degree Contraction Problem. ⋮ MSOL restricted contractibility to planar graphs ⋮ Paths to trees and cacti ⋮ On the parameterized complexity of contraction to generalization of trees ⋮ An improved linear kernel for the cycle contraction problem ⋮ Modification to Planarity is Fixed Parameter Tractable ⋮ On the Parameterized Complexity of Contraction to Generalization of Trees. ⋮ On the Parameterized Approximability of Contraction to Classes of Chordal Graphs ⋮ Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable
This page was built for publication: Obtaining planarity by contracting few edges
