Obtaining a Planar Graph by Vertex Deletion

Details Obtaining a Planar Graph by Vertex Deletion Obtaining a Planar Graph by Vertex Deletion

2008-12-29

arxiv.org/abs/0812.4919v1

Computer Science

Data Structures and Algorithms

16 pages, 4 figures. A preliminary version of this paper appeared in the proceedings of WG 2007 (33rd International Workshop o

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Obtaining a Planar Graph by Vertex Deletion does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Obtaining a Planar Graph by Vertex Deletion, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Obtaining a Planar Graph by Vertex Deletion will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-448901