Obtaining a Planar Graph by Vertex Deletion

Obtaining a Planar Graph by Vertex Deletion

0.00 Avg rating0 Votes
Article ID: iaor2012413
Volume: 62
Issue: 3
Start Page Number: 807
End Page Number: 822
Publication Date: Apr 2012
Journal: Algorithmica
Authors: ,
Keywords: programming: quadratic
Abstract:

In the kApex problem the task is to find at most k vertices whose deletion makes the given graph planar. The graphs for which there exists a solution form a minor closed class of graphs, hence by the deep results of Robertson and Seymour (J. Comb. Theory, Ser. B 63(1):65–110, 1995; J. Comb. Theory, Ser. B 92(2):325–357, 2004), there is a cubic algorithm for every fixed value of k. However, the proof is extremely complicated and the constants hidden by the big‐O notation are huge. Here we give a much simpler algorithm for this problem with quadratic running time, by iteratively reducing the input graph and then applying techniques for graphs of bounded treewidth.

Reviews

Required fields are marked *. Your email address will not be published.