de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Journal Article

Connecting Face Hitting Sets in Planar Graphs

MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons45438

Schweitzer,  Pascal
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Locator
There are no locators available
Fulltext (public)
There are no public fulltexts available
Supplementary Material (public)
There is no public supplementary material available
Citation

Schweitzer, P., & Schweitzer, P. (2010). Connecting Face Hitting Sets in Planar Graphs. Information Processing Letters, 111(1), 11-15. doi:10.1016/j.ipl.2010.10.008.


Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-162F-4
Abstract
We show that any face hitting set of size n of a connected planar graph with a minimum degree of at least 3 is contained in a connected subgraph of size 5n−6. Furthermore we show that this bound is tight by providing a lower bound in the form of a family of graphs. This improves the previously known upper and lower bound of 11n−18 and 3n respectively by Grigoriev and Sitters. Our proof is valid for simple graphs with loops and generalizes to graphs embedded in surfaces of arbitrary genus.