Guarding Quadrangulations and Stacked Triangulations with Edges

Paul Jungeblut, Torsten Ueckerdt

Introduction

The classic "Art Gallery Problem" asks for the minimum number of stationary guards needed to observe every point in an $n$-sided polygon. In graph theory, this problem translates to finding a set of guards (vertices or edges) that "see" all faces of a planar graph. This paper investigates edge guarding in two specific classes of planar graphs: quadrangulations and stacked triangulations. An edge $vw$ is said to guard a face if at least one of its endpoints, $v$ or $w$, is incident to that face.

Guarding Quadrangulations

A quadrangulation is a planar graph where every face is a 4-cycle. While general planar graphs are known to require up to $\lfloor n/3 \rfloor$ edge guards, the authors explore whether the regular structure of quadrangulations allows for a lower bound.

An example of an edge-guarding set in a quadrangulation, where thick purple lines represent the guarding edges.

To establish the $\lfloor n/3 \rfloor$ upper bound, the authors utilize the properties of the dual graph. Since every face in a quadrangulation has four edges, the dual graph is 4-regular. By applying Petersen’s 2-Factor Theorem, the dual graph can be decomposed into vertex-disjoint cycles. This structural insight allows for a specific vertex coloring that ensures every face is incident to a monochromatic edge, effectively guarding the entire graph with at most $n/3$ edges.

Stacked Triangulations

Stacked triangulations, also known as Apollonian networks, are formed by recursively adding a vertex inside a face and connecting it to the three vertices of that face. This recursive nature makes them significantly easier to guard than general triangulations.

Recursive stacking operations (a) $\Delta_3$ and (b) $\Delta_2$ used to construct stacked triangulations by inserting vertices into existing faces.

The authors prove a tight bound of $\lfloor 2n/7 \rfloor$ for this class. The proof relies on an inductive structural analysis: identifying minimal configurations (like those shown in the stacking operations above), removing them to apply an inductive hypothesis, and then extending the guard set back to the original graph. This result is a notable improvement over the $\lfloor n/3 \rfloor$ bound required for general triangulations.

Key Results and Complexity

The paper's findings are summarized in the table below, showing both the necessity (lower bound) and sufficiency (upper bound) of edge guards for $n$-vertex graphs:

Graph Class Lower Bound Upper Bound Complexity
Quadrangulation $\lfloor (n-2)/4 \rfloor$ $\lfloor n/3 \rfloor$ $O(n^{3/2})$
2-Degenerate Quad $\lfloor (n-2)/4 \rfloor$ $\lfloor n/4 \rfloor$ (Tight) $O(n)$
Stacked Triangulation $\lceil (2n-4)/7 \rceil$ $\lfloor 2n/7 \rfloor$ (Tight) $O(n)$

Conclusion

This work provides tight bounds for stacked triangulations and 2-degenerate quadrangulations, while significantly narrowing the gap for general quadrangulations. A primary open question remains: can the upper bound for quadrangulations be improved from $n/3$ to something closer to the $n/4$ lower bound? Additionally, the techniques used for stacked triangulations may provide a roadmap for improving bounds on more complex 4-connected triangulations.

Summary updated

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