Elimination distance to bounded degree on planar graphsArticle
Authors: Alexander Lindermayr ; Sebastian Siebertz ; Alexandre Vigny
NULL##NULL##NULL
Alexander Lindermayr;Sebastian Siebertz;Alexandre Vigny
We study the graph parameter elimination distance to bounded degree, which
was introduced by Bulian and Dawar in their study of the parameterized
complexity of the graph isomorphism problem. We prove that the problem is
fixed-parameter tractable on planar graphs, that is, there exists an algorithm
that given a planar graph G and integers d and k decides in time
f(k,d)⋅nc for a computable function~f and constant c whether the
elimination distance of G to the class of degree d graphs is at most k.