Improved bounds for guarding plane graphs with edges
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 2 5 n edges, then extend this approach with a deeper analysis to yield an improved bound of 3 8 n 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 su ce, removing the dependence on α.
|Keywords||Four-color theorem, Graph coloring, Phrases edge guards|
|Conference||16th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2018|
Biniaz, A. (Ahmad), Bose, P, Ooms, A. (Aurélien), & Verdonschot, S. (Sander). (2018). Improved bounds for guarding plane graphs with edges. In Leibniz International Proceedings in Informatics, LIPIcs (pp. 141–1412). doi:10.4230/LIPIcs.SWAT.2018.14