EUVIMEDEUVIMED entdecken
Crossref

Face-hitting dominating sets in planar graphs: Alternative proof and linear-time algorithm

Therese Biedl

Discrete Mathematics & Theoretical Computer Science · 17.08.2026 · vol. 28:4, SOFSEM 2026 (Special issues)

DOI: 10.46298/dmtcs.17747 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Discrete Mathematics & Theoretical Computer Science, online erschienen am 17.08.2026. Verfasst von Therese Biedl.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

In a recent paper, Francis, Illickan, Jose and Rajendraprasad showed that every $n$-vertex plane graph $G$ has (under some natural restrictions) a vertex-partition into two sets $V_1$ and $V_2$ such that each $V_i$ is \emph{dominating} (every vertex of $G$ contains a vertex of $V_i$ in its closed neighbourhood) and \emph{face-hitting} (every face of $G$ is incident to a vertex of $V_i$). Their proof works by considering a supergraph $G'$ of $G$ that has certain properties, and among all such graphs, taking one that has the fewest edges. As such, their proof is not algorithmic. Their proof also relies on the 4-color theorem, for which a quadratic-time algorithm exists, but it would not be easy to implement. In this paper, we give a new proof that every $n$-vertex plane graph $G$ has (under the same restrictions) a vertex-partition into two dominating face-hitting sets. Our proof is constructive, and requires nothing more complicated than splitting a graph into 2-connected components, finding an ear decomposition, and computing a perfect matching in a 3-regular plane graph. For all these problems, linear-time algorithms are known and so we can find the vertex-partition in linear time. Preliminary version appeared at SOFSEM 2026

Zitieren

APA

Biedl, T. (2026). Face-hitting dominating sets in planar graphs: Alternative proof and linear-time algorithm. Discrete Mathematics & Theoretical Computer Science, vol. 28:4, SOFSEM 2026(Special issues). https://doi.org/10.46298/dmtcs.17747

Vancouver

Biedl T. Face-hitting dominating sets in planar graphs: Alternative proof and linear-time algorithm. Discrete Mathematics & Theoretical Computer Science. 2026;vol. 28:4, SOFSEM 2026(Special issues). doi:10.46298/dmtcs.17747

BibTeX
@article{Biedl2026,
  author = {Biedl, Therese},
  title = {Face-hitting dominating sets in planar graphs: Alternative proof and linear-time algorithm},
  journal = {Discrete Mathematics & Theoretical Computer Science},
  year = {2026},
  volume = {vol. 28:4, SOFSEM 2026},
  number = {Special issues},
  doi = {10.46298/dmtcs.17747}
}
Kostenlos starten →