TY - GEN

T1 - An algorithm for finding large induced planar subgraphs

AU - Edwards, Keith

AU - Farr, Graham

PY - 2002

Y1 - 2002

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84867440440&partnerID=8YFLogxK

U2 - 10.1007/3-540-45848-4_6

DO - 10.1007/3-540-45848-4_6

M3 - Conference contribution

AN - SCOPUS:84867440440

SN - 9783540433095

SN - 3540433090

T3 - Lecture notes in computer science

SP - 75

EP - 83

BT - Graph Drawing

A2 - Mutzel, Petra

A2 - Junger, Michael

A2 - Leipert, Sebastian

PB - Springer

CY - Berlin

T2 - 9th International Symposium on Graph Drawing

Y2 - 23 September 2001 through 26 September 2001

ER -