Abstract
This paper presents an efficient algorithm that finds an induced planar subgraph of at least 3n/(d + 1) vertices in a graph of n vertices and maximum degree d. This bound is sharp for d = 3, in the sense that if ɛ > 3/4 then there are graphs of maximum degree 3 with no induced planar subgraph of at least ɛn vertices. Our performance ratios appear to be the best known for small d. For example, when d = 3, our performance ratio of at least 3/4 compares with the ratio 1/2 obtained by Halldórsson and Lau. Our algorithm builds up an induced planar subgraph by iteratively adding a new vertex to it, or swapping a vertex in it with one outside it, in such a way that the procedure is guaranteed to stop, and so as to preserve certain properties that allow its performance to be analysed. This work is related to the authors’ work on fragmentability of graphs.
Original language  English 

Title of host publication  Graph Drawing 
Subtitle of host publication  9th International Symposium, GD 2001 Vienna, Austria, September 2326, 2001 Revised Papers 
Editors  Petra Mutzel, Michael Junger, Sebastian Leipert 
Place of Publication  Berlin Germany 
Publisher  Springer 
Pages  7583 
Number of pages  9 
ISBN (Print)  3540433090 
DOIs  
Publication status  Published  2002 
Event  Graph Drawing 2001  Vienna, Austria Duration: 23 Sep 2001 → 26 Sep 2001 Conference number: 9th https://link.springer.com/book/10.1007/3540458484 (Proceedings) 
Publication series
Name  Lecture Notes in Computer Science 

Publisher  Springer 
Volume  2265 
ISSN (Print)  03029743 
Conference
Conference  Graph Drawing 2001 

Abbreviated title  GD 2001 
Country  Austria 
City  Vienna 
Period  23/09/01 → 26/09/01 
Internet address 

Cite this
Edwards, K., & Farr, G. E. (2002). An algorithm for finding large induced planar subgraphs. In P. Mutzel, M. Junger, & S. Leipert (Eds.), Graph Drawing: 9th International Symposium, GD 2001 Vienna, Austria, September 2326, 2001 Revised Papers (pp. 7583). (Lecture Notes in Computer Science; Vol. 2265). Springer. https://doi.org/10.1007/3540458484_6