Improved Bounds for Guarding Plane Graphs with Edges

Abstract

An edge guard set of a plane graph G is a subset Γ of edges of G such that each face of G is incident on an endpoint of an edge in Γ. 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 the same approach 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+α/9 edges, where α is the number of quadrilateral faces in G. This improves the previous bound of n/3+α 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 α.