Connected feedback vertex set in planar graphs

Alexander Grigoriev, René Sitters

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

Abstract

We study the problem of finding a minimum tree spanning the faces of a given planar graph. We show that a constant factor approximation follows from the unconnected version if the minimum degree is 3. Moreover, we present a polynomial time approximation scheme for both the connected and unconnected version.

Original languageEnglish
Title of host publicationGraph-Theoretic Concepts in Computer Science - 35th International Workshop, WG 2009, Revised Papers
Pages143-153
Number of pages11
Volume5911 LNCS
DOIs
Publication statusPublished - 2010
Event35th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2009 - Montpellier, France
Duration: 24 Jun 200926 Jun 2009

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5911 LNCS
ISSN (Print)03029743
ISSN (Electronic)16113349

Conference

Conference35th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2009
CountryFrance
CityMontpellier
Period24/06/0926/06/09

Fingerprint

Feedback Vertex Set
Polynomial Time Approximation Scheme
Connected Set
Minimum Spanning Tree
Minimum Degree
Planar graph
Polynomials
Face
Feedback
Approximation

Cite this

Grigoriev, A., & Sitters, R. (2010). Connected feedback vertex set in planar graphs. In Graph-Theoretic Concepts in Computer Science - 35th International Workshop, WG 2009, Revised Papers (Vol. 5911 LNCS, pp. 143-153). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5911 LNCS). https://doi.org/10.1007/978-3-642-11409-0_13
Grigoriev, Alexander ; Sitters, René. / Connected feedback vertex set in planar graphs. Graph-Theoretic Concepts in Computer Science - 35th International Workshop, WG 2009, Revised Papers. Vol. 5911 LNCS 2010. pp. 143-153 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{109abcad552842c880df78150c3a833b,
title = "Connected feedback vertex set in planar graphs",
abstract = "We study the problem of finding a minimum tree spanning the faces of a given planar graph. We show that a constant factor approximation follows from the unconnected version if the minimum degree is 3. Moreover, we present a polynomial time approximation scheme for both the connected and unconnected version.",
author = "Alexander Grigoriev and Ren{\'e} Sitters",
year = "2010",
doi = "10.1007/978-3-642-11409-0_13",
language = "English",
isbn = "3642114083",
volume = "5911 LNCS",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "143--153",
booktitle = "Graph-Theoretic Concepts in Computer Science - 35th International Workshop, WG 2009, Revised Papers",

}

Grigoriev, A & Sitters, R 2010, Connected feedback vertex set in planar graphs. in Graph-Theoretic Concepts in Computer Science - 35th International Workshop, WG 2009, Revised Papers. vol. 5911 LNCS, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5911 LNCS, pp. 143-153, 35th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2009, Montpellier, France, 24/06/09. https://doi.org/10.1007/978-3-642-11409-0_13

Connected feedback vertex set in planar graphs. / Grigoriev, Alexander; Sitters, René.

Graph-Theoretic Concepts in Computer Science - 35th International Workshop, WG 2009, Revised Papers. Vol. 5911 LNCS 2010. p. 143-153 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5911 LNCS).

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

TY - GEN

T1 - Connected feedback vertex set in planar graphs

AU - Grigoriev, Alexander

AU - Sitters, René

PY - 2010

Y1 - 2010

N2 - We study the problem of finding a minimum tree spanning the faces of a given planar graph. We show that a constant factor approximation follows from the unconnected version if the minimum degree is 3. Moreover, we present a polynomial time approximation scheme for both the connected and unconnected version.

AB - We study the problem of finding a minimum tree spanning the faces of a given planar graph. We show that a constant factor approximation follows from the unconnected version if the minimum degree is 3. Moreover, we present a polynomial time approximation scheme for both the connected and unconnected version.

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

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

U2 - 10.1007/978-3-642-11409-0_13

DO - 10.1007/978-3-642-11409-0_13

M3 - Conference contribution

SN - 3642114083

SN - 9783642114083

VL - 5911 LNCS

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 143

EP - 153

BT - Graph-Theoretic Concepts in Computer Science - 35th International Workshop, WG 2009, Revised Papers

ER -

Grigoriev A, Sitters R. Connected feedback vertex set in planar graphs. In Graph-Theoretic Concepts in Computer Science - 35th International Workshop, WG 2009, Revised Papers. Vol. 5911 LNCS. 2010. p. 143-153. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-642-11409-0_13