Obtaining Planarity by Contracting Few Edges
classification
💻 cs.DS
cs.DMmath.CO
keywords
planarproblemcontractingcontractioncontractionsedgeedgesfixed-parameter
read the original abstract
The Planar Contraction problem is to test whether a given graph can be made planar by using at most k edge contractions. This problem is known to be NP-complete. We show that it is fixed-parameter tractable when parameterized by k.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.