Connected feedback vertex set in planar graphs

Alexander Grigoriev*, René Sitters

*Corresponding author for this work

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 Dive into the research topics of 'Connected feedback vertex set in planar graphs'. Together they form a unique fingerprint.

Cite this