An algorithm for finding large induced planar subgraphs

Keith Edwards; Graham E Farr

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

An algorithm for finding large induced planar subgraphs

Keith Edwards, Graham E Farr

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

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 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 23-26, 2001 Revised Papers
Editors	Petra Mutzel, Michael Junger, Sebastian Leipert
Place of Publication	Berlin Germany
Publisher	Springer
Pages	75-83
Number of pages	9
ISBN (Print)	3540433090
DOIs	https://doi.org/10.1007/3-540-45848-4_6
Publication status	Published - 2002
Event	Graph Drawing 2001 - Vienna, Austria Duration: 23 Sept 2001 → 26 Sept 2001 Conference number: 9th https://link.springer.com/book/10.1007/3-540-45848-4 (Proceedings)

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	2265
ISSN (Print)	0302-9743

Conference

Conference	Graph Drawing 2001
Abbreviated title	GD 2001
Country/Territory	Austria
City	Vienna
Period	23/09/01 → 26/09/01
Internet address	https://link.springer.com/book/10.1007/3-540-45848-4 (Proceedings)

Access to Document

10.1007/3-540-45848-4_6

Cite this

@inproceedings{77b29cd02fb1471384c557987b32da48,

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 Halld{\'o}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{\textquoteright} work on fragmentability of graphs.",

author = "Keith Edwards and Farr, {Graham E}",

year = "2002",

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

language = "English",

isbn = "3540433090",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "75--83",

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

booktitle = "Graph Drawing",

note = "Graph Drawing 2001, GD 2001 ; Conference date: 23-09-2001 Through 26-09-2001",

url = "https://link.springer.com/book/10.1007/3-540-45848-4",

}

Edwards, K & Farr, GE 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 Germany, pp. 75-83, Graph Drawing 2001, 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 E.
Graph Drawing: 9th International Symposium, GD 2001 Vienna, Austria, September 23-26, 2001 Revised Papers. ed. / Petra Mutzel; Michael Junger; Sebastian Leipert. Berlin Germany: Springer, 2002. p. 75-83 (Lecture Notes in Computer Science; Vol. 2265).

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

TY - GEN

T1 - An algorithm for finding large induced planar subgraphs

AU - Edwards, Keith

AU - Farr, Graham E

N1 - Conference code: 9th

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

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

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

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

M3 - Conference Paper

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 Germany

T2 - Graph Drawing 2001

Y2 - 23 September 2001 through 26 September 2001

ER -