Biniaz, Ahmad ;
Bose, Prosenjit ;
Ooms, Aurélien ;
Verdonschot, Sander
Improved Bounds for Guarding Plane Graphs with Edges
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 nvertex embedded planar graph G:
1) We present a simple inductive proof for a theorem of Everett and RiveraCampo (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:114:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770682},
ISSN = {18688969},
year = {2018},
volume = {101},
editor = {David Eppstein},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8840},
URN = {urn:nbn:de:0030drops88403},
doi = {10.4230/LIPIcs.SWAT.2018.14},
annote = {Keywords: edge guards, graph coloring, fourcolor theorem}
}
2018
Keywords: 

edge guards, graph coloring, fourcolor theorem 
Seminar: 

16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)

Issue date: 

2018 
Date of publication: 

2018 