KIT | KIT-Bibliothek | Impressum | Datenschutz

Guarding Quadrangulations and Stacked Triangulations with Edges

Jungeblut, Paul; Ueckerdt, Torsten

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.

DOI: 10.1007/978-3-030-60440-0_2
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Proceedingsbeitrag
Publikationsjahr 2020
Sprache Englisch
Identifikator ISBN: 978-3-030-60440-0
KITopen-ID: 1000120594
Erschienen in Proceedings of the 46th International Workshop on Graph-Theoretic Concepts in Computer Science
Veranstaltung 46th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2020), Online, 24.06.2020 – 26.06.2020
Verlag Springer
Bemerkung zur Veröffentlichung Die Veranstaltung fand wegen der Corona-Pandemie als Online-Event statt
Nachgewiesen in Dimensions
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page