Guarding Quadrangulations and Stacked Triangulations with Edges

Paul Jungeblut, Torsten Ueckerdt

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.
BibTeX
@inproceedings{jungeblut2020guarding,
  author = {Paul Jungeblut and Torsten Ueckerdt},
  title = {{Guarding Quadrangulations and Stacked Triangulations with Edges}},
  booktitle = {WG},
  year = {2020},
  url = {https://openreview.net/forum?id=vaIAC3o4t7b},
}
Figure