2025/08/15 by Therese Biedl, Biedl, Therese
Computer Science · #Computational Geometry and Mesh Generation #Advanced Graph Theory Research #Complexity and Algorithms in Graphs
paper · pdf · doi:10.48550/arxiv.2508.11444
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 V1 and V2 such that each Vi is dominating (every vertex of G contains a vertex of Vi in its closed neighbourhood) and face-hitting (every face of G is incident to a vertex of Vi). 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.