Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en Biniaz, Ahmad; Bose, Prosenjit; Ooms, Aurélien; Verdonschot, Sander http://www.dagstuhl.de/lipics License
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-88403
URL:

; ; ;

Improved Bounds for Guarding Plane Graphs with Edges

pdf-format:


Abstract

An edge guard set of a plane graph G is a subset Gamma of edges of G such that each face of G is incident to an endpoint of an edge in Gamma. Such a set is said to guard G. We improve the known upper bounds on the number of edges required to guard any n-vertex embedded planar graph G: 1) We present a simple inductive proof for a theorem of Everett and Rivera-Campo (1997) that G can be guarded with at most 2n/5 edges, then extend this approach with a deeper analysis to yield an improved bound of 3n/8 edges for any plane graph. 2) We prove that there exists an edge guard set of G with at most n/(3) + alpha/9 edges, where alpha is the number of quadrilateral faces in G. This improves the previous bound of n/(3) + alpha by Bose, Kirkpatrick, and Li (2003). Moreover, if there is no short path between any two quadrilateral faces in G, we show that n/(3) edges suffice, removing the dependence on alpha.

BibTeX - Entry

@InProceedings{biniaz_et_al:LIPIcs:2018:8840,
  author =	{Ahmad Biniaz and Prosenjit Bose and Aur{\'e}lien Ooms and Sander Verdonschot},
  title =	{{Improved Bounds for Guarding Plane Graphs with Edges}},
  booktitle =	{16th Scandinavian Symposium and Workshops on Algorithm  Theory (SWAT 2018)},
  pages =	{14:1--14:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-068-2},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{101},
  editor =	{David Eppstein},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8840},
  URN =		{urn:nbn:de:0030-drops-88403},
  doi =		{10.4230/LIPIcs.SWAT.2018.14},
  annote =	{Keywords: edge guards, graph coloring, four-color theorem}
}

Keywords: edge guards, graph coloring, four-color theorem
Seminar: 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)
Issue date: 2018
Date of publication: 2018


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI