2008/12/29 by Dániel Marx, Marx, Dániel, Ildikó Schlotter +1 · 1 citation
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Graph Labeling and Dimension Problems #cs.DS
paper · pdf · doi:10.48550/arxiv.0812.4919
16 pages, 4 figures. A preliminary version of this paper appeared in the proceedings of WG 2007 (33rd International Workshop on Graph-Theoretic Concepts in Computer Science). The paper has been submitted to Algorithmica
arxiv created 2008/12/29 · openalex publication_date 2008/12/29 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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, there is an O(n3) time 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.