Editing to a planar graph of given degrees

作者：

Highlights：

• We study Deletion to a Planar Graph of Given Degrees and its connected variant.

• These problems are known to be NP-complete and W[1]-hard for general graphs.

• We construct polynomial kernels for both problems when restricted to planar graphs.

摘要

•We study Deletion to a Planar Graph of Given Degrees and its connected variant.•These problems are known to be NP-complete and W[1]-hard for general graphs.•We construct polynomial kernels for both problems when restricted to planar graphs.

论文关键词：Graph editing,Connected graph,Planar graph,Polynomial kernel

论文评审过程：Received 21 February 2016, Revised 17 November 2016, Accepted 26 November 2016, Available online 1 December 2016, Version of Record 19 December 2016.

论文官网地址：https://doi.org/10.1016/j.jcss.2016.11.009