In a recent paper, Francis, Illickan, Jose, and Rajendraprasad showed that every $n$-vertex plane graph $G$ can be partitioned into two sets $V_1$ and $V_2$ under certain natural restrictions, such that each $V_i$ is
- dominating (every vertex of $G$ has a vertex of $V_i$ in its closed neighborhood)
- face-hitting (every face of $G$ is incident to a vertex of $V_i$).
Their proof works by considering a supergraph $G'$ of $G$ with specific properties and selecting one with the fewest edges among all such graphs. However, their proof is non-algorithmic and relies on the 4-color theorem, which has a quadratic-time algorithm that is not easy to implement.
In this paper, we provide a new proof that every $n$-vertex plane graph $G$ can also be partitioned into two dominating face-hitting sets under the same restrictions. Our proof is constructive and only requires splitting the graph into 2-connected components, finding an ear decomposition, and computing a perfect matching in a 3-regular plane graph. All these problems have known linear-time algorithms, allowing us to find the vertex partition in linear time.
Blogger's Review: This paper presents a novel constructive proof that overcomes the limitations of traditional complex algorithms. By integrating classical graph theory problems with linear-time algorithms, it demonstrates the efficiency of face-hitting dominating sets in planar graphs, highlighting its significant theoretical and practical applications. The linear-time solution is particularly valuable for large-scale graph processing.