Obtaining Planarity by Contracting Few Edges

Daniel Paulusma; Petr A. Golovach; Pim van 't Hof

REVIEW

Obtaining Planarity by Contracting Few Edges

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 1204.5113 v1 pith:MIYDGYR4 submitted 2012-04-23 cs.DS cs.DMmath.CO

Petr A. Golovach , Pim van 't Hof , Daniel Paulusma This is my paper · ORCID

classification cs.DScs.DMmath.CO

keywords planarproblemcontractingcontractioncontractionsedgeedgesfixed-parameter

verification ladder T0 review T1 audit T2 compute T3 formal

0 comments

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.

Discussion (0). Continue with ORCID to comment.

Pith tools