在最近的一篇论文中，Francis、Illickan、Jose 和 Rajendraprasad 表明，每个 $n$ 顶点的平面图 $G$ 在一些自然限制下，可以将其顶点划分为两个集合 $V_1$ 和 $V_2$，使得每个 $V_i$ 都是
- 主导集（$G$ 的每个顶点在 $V_i$ 的闭邻域内都有一个顶点）
- 面击集（$G$ 的每个面都与 $V_i$ 的一个顶点相接）。
他们的证明通过考虑一个具有特定属性的超图 $G'$，并在所有此类图中选择边数最少的一个。然而，这种证明并不具备算法性质，并且依赖于四色定理，虽然存在一个二次时间的算法，但实现起来并不简单。
在本文中，我们提供了一个新证明，证明每个 $n$ 顶点的平面图 $G$ 在相同限制下可以划分为两个主导的面击集。我们的证明是构造性的，仅需通过将图分割为 2-连通分量、寻找耳分解以及计算 3-正则平面图的完美匹配来实现。这些问题都有已知的线性时间算法，因此我们可以在线性时间内找到顶点划分。
博主点评： 本文提供了一种新的构造性证明，突破了传统的依赖复杂算法的限制。通过将图论中的经典问题与线性时间算法相结合，展示了平面图中面击主导集的有效性，具有重要的理论与实际应用价值。尤其是在大规模图处理方面，线性时间的解决方案显得尤为重要。