2020/06/24 by Paul Jungeblut, Jungeblut, Paul, Torsten Ueckerdt +1
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.2006.13722
openalex publication_date 2020/06/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let G = (V,E) be a plane graph. A face f of G is guarded by an edge vw ∈ E if at least one vertex from \v,w\ is on the boundary of f. For a planar graph class G we ask for the minimal number of edges needed to guard all faces of any n-vertex graph in 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.