We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

A linear kernel for finding square roots of almost planar graphs.

Golovach, P.A. and Kratsch, D. and Paulusma, D. and Stewart, A. (2016) 'A linear kernel for finding square roots of almost planar graphs.', in 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). Wadern: Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, p. 4. Leibniz International Proceedings in Informatics (LIPIcs). (53).


A graph H is a square root of a graph G if G can be obtained from H by the addition of edges between any two vertices in H that are of distance 2 of each other. The Square Root problem is that of deciding whether a given graph admits a square root. We consider this problem for planar graphs in the context of the "distance from triviality" framework. For an integer k, a planar+kv graph is a graph that can be made planar by the removal of at most k vertices. We prove that the generalization of Square Root, in which we are given two subsets of edges prescribed to be in or out of a square root, respectively, has a kernel of size O(k) for planar+kv graphs, when parameterized by k. Our result is based on a new edge reduction rule which, as we shall also show, has a wider applicability for the Square Root problem.

Item Type:Book chapter
Full text:(VoR) Version of Record
Available under License - Creative Commons Attribution.
Download PDF
Publisher Web site:
Publisher statement:© Petr A. Golovach, Dieter Kratsch, Daniël Paulusma, and Anthony Stewart; licensed under Creative Commons License CC-BY
Date accepted:01 April 2016
Date deposited:01 July 2016
Date of first online publication:June 2016
Date first made open access:No date available

Save or Share this output

Look up in GoogleScholar