### 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 Halldorsson and Lau. Our algorithm builds up an induced planar subgraph by iteratively adding a newvertex 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 23–26, 2001 Revised Papers |

Editors | Petra Mutzel, Michael Junger, Sebastian Leipert |

Place of Publication | Berlin |

Publisher | Springer |

Pages | 75-83 |

Number of pages | 9 |

ISBN (Electronic) | 9783540458487 |

ISBN (Print) | 9783540433095, 3540433090 |

DOIs | |

Publication status | Published - 2002 |

Event | 9th International Symposium on Graph Drawing - Vienna, Austria Duration: 23 Sep 2001 → 26 Sep 2001 |

### Publication series

Name | Lecture notes in computer science |
---|---|

Publisher | Springer |

Volume | 2265 |

ISSN (Print) | 0302-9743 |

### Conference

Conference | 9th International Symposium on Graph Drawing |
---|---|

Abbreviated title | GD 2001 |

Country | Austria |

City | Vienna |

Period | 23/09/01 → 26/09/01 |

## Fingerprint Dive into the research topics of 'An algorithm for finding large induced planar subgraphs'. Together they form a unique fingerprint.

## Cite this

Edwards, K., & Farr, G. (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 23–26, 2001 Revised Papers*(pp. 75-83). (Lecture notes in computer science ; Vol. 2265). Springer . https://doi.org/10.1007/3-540-45848-4_6