{"ID":2881944,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2508.11444","arxiv_id":"2508.11444","title":"Face-hitting dominating sets in planar graphs: Alternative proof and linear-time algorithm","abstract":"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.","short_abstract":"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 \\em...","url_abs":"https://arxiv.org/abs/2508.11444","url_pdf":"https://arxiv.org/pdf/2508.11444v2","authors":"[\"Therese Biedl\"]","published":"2025-08-15T12:49:38Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"math.CO\"]","methods":"[]","has_code":false}