Obtaining a Planar Graph by Vertex Deletion |
| |
Authors: | Dániel Marx Ildikó Schlotter |
| |
Affiliation: | 1. Department of Computer Science and Information Theory, Budapest University of Technology and Economics, Budapest, 1521, Hungary
|
| |
Abstract: | In the?k-Apex 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|