Answers are grounded in this paper and cite their sources.
Demonstrates a polynomial kernel for the Face Cover Number problem in planar graphs, indicating a significant advancement in graph theory.
Given a planar graph, a subset of its vertices called terminals, and k ∈ ℕ, the Face Cover Number problem asks whether the terminals lie on the boundaries of at most k faces of some embedding of the input graph. When a plane graph is given in the input, the problem is known to have a polynomial kernel [Valentin Garnero et al., 2017]. In this paper, we present the first polynomial kernel for Face Cover Number when the input is a planar graph (without a fixed embedding). Our approach overcomes the challenge of not having a predefined set of face boundaries by building a kernel bottom-up on an SPR-tree while preserving the essential properties of the face cover along the way.
No takes yet. Share an insight, caveat, or question.
Hamm et al. (2026) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: