Obtaining a Planar Graph by Vertex Deletion
| dc.creator | Marx, Dániel | |
| dc.creator | Schlotter, Ildikó | |
| dc.date | 2008-12-29 | |
| dc.date.accessioned | 2026-07-07T12:23:01Z | |
| dc.date.available | 2026-07-07T12:23:01Z | |
| dc.description | 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(n^3) 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. | |
| dc.description | 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 | |
| dc.identifier | https://arxiv.org/abs/0812.4919 | |
| dc.identifier | http://arxiv.org/abs/0812.4919 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/213852 | |
| dc.subject | Data Structures and Algorithms | |
| dc.title | Obtaining a Planar Graph by Vertex Deletion | |
| dc.type | text |