A linear kernel for finding square roots of almost planar graphs

DOI10.1016/J.TCS.2017.05.008zbMATH Open1372.05052arXiv1608.06136OpenAlexW2963073869MaRDI QIDQ2402259FDOQ2402259

Authors: Dieter Kratsch, Daniël Paulusma, Anthony Stewart, Petr A. Golovach 

Publication date: 7 September 2017

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: 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 from 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 (or k-apex graph) is a graph that can be made planar by the removal of at most k vertices. We prove that a generalization of Square Root, in which some edges are prescribed to be either in or out of any solution, 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.

Full work available at URL: https://arxiv.org/abs/1608.06136

Recommendations

• A linear kernel for finding square roots of almost planar graphs
• Parameterized algorithms for finding square roots
• Graph square roots of small distance from degree one graphs
• Computing square roots of graphs with low maximum degree
• Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2

zbMATH Keywords

square rootlinear kernel\(k\)-apex graphs

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10)

Cites Work

• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Computing roots of graphs is hard
• A good characterization of squares of strongly chordal split graphs
• Complexity of finding graph roots with girth conditions
• Computing square roots of trivially perfect and threshold graphs
• Parameterized algorithms for finding square roots
• Sparse square roots
• Bipartite roots of graphs
• Title not available (Why is that?)
• Recognizing Powers of Proper Interval, Split, and Chordal Graphs
• Algorithms for Square Roots of Graphs
• Title not available (Why is that?)
• Parameterized algorithms
• Uniqueness of graph square roots of girth six
• The square root of a graph
• Title not available (Why is that?)
• The square of a block graph
• Parameterized and Exact Computation
• The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
• A unified approach to recognize squares of split graphs
• A characterization of line graphs that are squares of graphs
• Square roots of minor closed graph classes
• Squares of low clique number
• A linear kernel for finding square roots of almost planar graphs
• Computing square roots of graphs with low maximum degree
• Finding cactus roots in polynomial time
• A criterion for planarity of the square of a graph

Cited In (5)

• A linear kernel for finding square roots of almost planar graphs
• Finding cactus roots in polynomial time
• Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2
• Graph square roots of small distance from degree one graphs
• Finding cut-vertices in the square roots of a graph

This page was built for publication: A linear kernel for finding square roots of almost planar graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2402259)