2018/04/19 by Ahmad Biniaz, Prosenjit Bose, Biniaz, Ahmad +5
Computer Science · Engineering · #Computational Geometry and Mesh Generation #Advanced Graph Theory Research #Optimization and Packing Problems
paper · pdf · doi:10.48550/arxiv.1804.07150
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 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)+\fracα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 α.