An edge guard set of a plane graph G is a subset Γ of edges of G such that each face of G is incident to an endpoint of an edge in Γ. Such a set is said to guardG. 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 (Comput Geom Theory Appl 7:201–203, 1997) that G can be guarded with at most 2n5 edges, then extend this approach with a deeper analysis to yield an improved bound of 3n8 edges for any plane graph. (2) We prove that there exists an edge guard set of G with at most n3+α9 edges, where α is the number of quadrilateral faces in G. This improves the previous bound of n3+α by Bose et al. (Comput Geom Theory Appl 26(3):209–219, 2003). Moreover, if there is no short path between any two quadrilateral faces in G, we show that n3 edges suffice, removing the dependence on α.

Edge guards, Four-color theorem, Graph coloring
Graphs and Combinatorics
School of Computer Science

Biniaz, A. (Ahmad), Bose, P, Ooms, A. (Aurélien), & Verdonschot, S. (Sander). (2019). Improved Bounds for Guarding Plane Graphs with Edges. Graphs and Combinatorics. doi:10.1007/s00373-018-02004-z