An algorithm for finding large induced planar subgraphs

Keith Edwards; Graham Farr

doi:10.1007/3-540-45848-4_6

An algorithm for finding large induced planar subgraphs

Keith Edwards, Graham Farr

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

8 Citations (Scopus)

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	https://doi.org/10.1007/3-540-45848-4_6
Publication status	Published - 2002
Event	9th International Symposium on Graph Drawing - Vienna, Austria Duration: 23 Sept 2001 → 26 Sept 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/Territory	Austria
City	Vienna
Period	23/09/01 → 26/09/01

Access to Document

10.1007/3-540-45848-4_6

Cite this

@inproceedings{6ea7c60cf9244ca495975118a3af9f4b,

title = "An algorithm for finding large induced planar subgraphs",

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.",

author = "Keith Edwards and Graham Farr",

year = "2002",

doi = "10.1007/3-540-45848-4_6",

language = "English",

isbn = "9783540433095",

series = "Lecture notes in computer science ",

publisher = "Springer ",

pages = "75--83",

editor = "Petra Mutzel and Michael Junger and Sebastian Leipert",

booktitle = "Graph Drawing",

note = "9th International Symposium on Graph Drawing, GD 2001 ; Conference date: 23-09-2001 Through 26-09-2001",

}

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. Lecture notes in computer science , vol. 2265, Springer , Berlin, pp. 75-83, 9th International Symposium on Graph Drawing, Vienna, Austria, 23/09/01. https://doi.org/10.1007/3-540-45848-4_6

An algorithm for finding large induced planar subgraphs. / Edwards, Keith; Farr, Graham.

Graph Drawing : 9th International Symposium, GD 2001 Vienna, Austria, September 23–26, 2001 Revised Papers. ed. / Petra Mutzel; Michael Junger; Sebastian Leipert. Berlin : Springer , 2002. p. 75-83 (Lecture notes in computer science ; Vol. 2265).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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 -

An algorithm for finding large induced planar subgraphs

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this