License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SWAT.2018.14
URN: urn:nbn:de:0030-drops-88403
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8840/
Go to the corresponding LIPIcs Volume Portal

Biniaz, Ahmad ; Bose, Prosenjit ; Ooms, Aurélien ; Verdonschot, Sander

Improved Bounds for Guarding Plane Graphs with Edges

pdf-format:
LIPIcs-SWAT-2018-14.pdf (0.8 MB)

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
Collection: 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)
Issue Date: 2018
Date of publication: 04.06.2018

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