Guarding Quadrangulations and Stacked Triangulations with Edges

Abstract

Let $G=(V,E)$ be a plane graph. A face $f$ of $G$ is guarded by an edge $vw\in E$ if at least one vertex from $\{v,w\}$ is on the boundary of $f$. For a planar graph class $\mathcal{G}$ we ask for the minimal number of edges needed to guard all faces of any $n$-vertex graph in $\mathcal{G}$. We prove that $\lfloor n/3\rfloor$ edges are always sufficient for quadrangulations and give a construction where $\lfloor (n-2)/4\rfloor$ edges are necessary. For $2$-degenerate quadrangulations we improve this to a tight upper bound of $\lfloor n/4\rfloor$ edges. We further prove that $\lfloor 2n/7\rfloor$ edges are always sufficient for stacked triangulations (that are the $3$-degenerate triangulations) and show that this is best possible up to a small additive constant.

17 pages, 9 figures, accepted for 46th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2020)